package LeetCode;

import org.apache.hadoop.io.DoubleWritable;

import java.util.*;

// 二叉树以及链表定义
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

}

class MedianFinder {
    private final PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a); // 最大堆
    private final PriorityQueue<Integer> right = new PriorityQueue<>(); // 最小堆

    public void addNum(int num) {
        if (left.size() == right.size()) {
            right.offer(num);
            left.offer(right.poll());
        } else {
            left.offer(num);
            right.offer(left.poll());
        }
    }

    public double findMedian() {
        if (left.size() > right.size()) {
            return left.peek();
        }
        return (left.peek() + right.peek()) / 2.0;
    }
}


class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue1.offer(x);
        while (!queue2.isEmpty()){
            queue1.offer(queue2.poll());
        }
        Queue<Integer> tmp = queue1;
        queue1 = queue2;
        queue2 = tmp;
    }

    public int pop() {
        return queue2.poll();
    }

    public int top() {
        return queue2.peek();
    }

    public boolean empty() {
        return queue2.isEmpty();
    }
}

class MyCircularDeque {
    private int[] arr;
    private int front;
    private int rear;
    private int size;

    public MyCircularDeque(int k) {
        size = k + 1;
        arr = new int[k + 1];
        front = 0;
        rear = 0;
    }

    public boolean insertFront(int value) {
        if (isFull()){
            return false;
        }
        else {
            front = (front - 1 + size) % size;
            arr[front] = value;
            return true;
        }
    }

    public boolean insertLast(int value) {
        if (isFull()){
            return false;
        }
        else {
            arr[rear] = value;
            rear = (rear + 1) % size;
            return true;
        }
    }

    public boolean deleteFront() {
        if (isEmpty()){
            return false;
        }
        else {
            front = (front + 1) % size;
            return true;
        }
    }

    public boolean deleteLast() {
        if (isEmpty()){
            return false;
        }
        else {
            rear = (rear - 1 + size) % size;
            return true;
        }
    }

    public int getFront() {
        if (isEmpty()){
            return -1;
        }
        else {
            return arr[front];
        }
    }

    public int getRear() {
        if (isEmpty()){
            return -1;
        }
        else {
            return arr[(rear - 1 + size) % size];
        }
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % size == front;
    }
}

class DLinkedNode {
    private int val;
    private DLinkedNode prev;
    private DLinkedNode next;

    public DLinkedNode() {}
    public DLinkedNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
    public DLinkedNode(int val, DLinkedNode prev, DLinkedNode next) {
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
}

class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {
            key = _key; value = _value;
        }
    }
    private Map<Integer, DLinkedNode> map = new HashMap<>();
    private DLinkedNode head, tail;
    private int size;
    private int capacity;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = map.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = map.get(key);
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode(key, value);
            map.put(key, newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                DLinkedNode tail = removeTail();
                map.remove(tail.key);
                size--;
            }
        }
        else {
            node.value = value;
            moveToHead(node);
        }
    }

    private DLinkedNode removeTail() {
        DLinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

}
class Edge {
    int target;
    int weight;

    Edge(int target, int weight) {
        this.target = target;
        this.weight = weight;
    }
}

class DijkstraAlgorithm {
    public static void dijkstra(List<List<Edge>> graph, int start) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist,Integer.MAX_VALUE);
        boolean[] visited = new boolean[n];
        dist[start] = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparing(e -> e.weight));
        pq.offer(new Edge(start, 0));

        while (!pq.isEmpty()){
            Edge curr = pq.poll();
            int u = curr.target;
            if (visited[u]) continue;
            visited[u] = true;

            for (Edge edge : graph.get(u)){
                int v = edge.target;
                int w = edge.weight;
                if (!visited[v] && dist[u] + w < dist[v]){
                    dist[v] = dist[u] + w;
                }
            }
        }

        // 打印结果
        System.out.println("最短路径结果：");
        for (int i = 0; i < n; i++) {
            System.out.println("从顶点 " + start + " 到顶点 " + i + " 的最短距离是：" + dist[i]);
        }
    }

    public static void main(String[] args) {
        int n = 5; // 顶点数
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 添加边
        graph.get(0).add(new Edge(1, 9));
        graph.get(0).add(new Edge(2, 6));
        graph.get(0).add(new Edge(3, 5));
        graph.get(0).add(new Edge(4, 3));
        graph.get(2).add(new Edge(1, 2));
        graph.get(2).add(new Edge(3, 4));

        dijkstra(graph, 0); // 从顶点0开始计算最短路径
    }
}
class FloydAlgorithm {
    public static void floyd(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][n];
        int INF = Integer.MAX_VALUE;

        // 初始化距离矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // 动态规划计算最短路径
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // 打印结果
        System.out.println("最短路径结果：");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print("从顶点 " + i + " 到顶点 " + j + " 的最短距离是：" + dist[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int n = 4; // 顶点数
        int[][] graph = {
                {0, 5, Integer.MAX_VALUE, 10},
                {Integer.MAX_VALUE, 0, 3, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 1},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        };

        floyd(graph); // 计算所有顶点对的最短路径
    }
}

class Solution {
    public static void main(String[] args) {


        int[] dist = {4, 2, 6, 3, 9};
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String word = "ABCE";

        // 创建Solution类的实例,以调用类中的非静态（static）方法
        // 或者将类中的方法使用 static 修饰，即标记为静态方法，即可被同样是static的main函数调用
         /* Todo 原理：
          main 方法是在类加载时由 JVM 直接调用的，而不是在创建类的实例之后调用的。
          因此，它不能直接访问非静态（实例）方法，因为这些方法需要一个类的实例来调用。**/
        Solution solution = new Solution();

        // 函数调用 DeBug
//        System.out.println(solution.findWinningPlayer(dist, 3));
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(6);
//        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian());
    }
    public boolean canBeValid(String s, String locked) {
        int len = s.length();
        if (len % 2 > 0) return false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++){
            if (stack.isEmpty() || s.charAt(i) == '('){
                stack.push(s.charAt(i));
            }
            else {
                if (')' == s.charAt(i)){
                    Character c = stack.pop();
                    if (c != '('){
                        if (locked.charAt(i) == '1')
                            return false;
                    }

                }
            }
        }
        return true;
    }

    public void fastSort(int[] arr, int low, int high) {

        if (low < high) {
            int baseIndex = findBaseIndex(arr, low, high);
            fastSort(arr, low, baseIndex - 1);
            fastSort(arr, baseIndex + 1, high);
        }

    }

    public  int findBaseIndex(int[] arrs, int low, int high) {
        int target = arrs[low];
        int i = low, j = high;

        while (i < j) {
            while (arrs[j] >= target) {
                j--;
            }
            while (arrs[i] <= target) {
                i++;
            }
            if (i < j) {
                int temp = arrs[i];
                arrs[i] = arrs[j];
                arrs[j] = temp;
            }
        }
        int temp = arrs[low];
        arrs[low] = arrs[i];
        arrs[i] = temp;

        return i;
    }
    public ListNode insertionSortList(ListNode head) {

        if (head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode curr = head.next, lastSorted = head;
        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            }
            else {
                ListNode prev = dummy;
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;
        }

        return dummy.next;
    }

    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {

        if (head == null) return head;
        if (head.next == tail) {
            head.next = null;
            return head;
        }

        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast!= tail) {
                fast = fast.next;
            }
        }

        ListNode mid = slow;
        ListNode left = sortList(head, mid);
        ListNode right = sortList(mid, tail);

        return merge(left, right);
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        ListNode temp1 = left, temp2 = right;
        while (temp1!= null && temp2!= null) {
            if (temp1.val < temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            }
            else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        }
        if (temp2 != null) {
            temp.next = temp2;
        }
        return dummy.next;
    }

    public int getWinner(int[] arr, int k) {
        int cnt = 0, helper = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > helper) {
                helper = arr[i];
                cnt = 0;
            }
            cnt++;
            if (k == cnt) break;
        }
        return helper;
    }

    public int hammingWeight(int n) {
        int cnt = 0;
//        while (n != 1) {
//            cnt += n % 2;
//            n /= 2;
//        }
//        return cnt + 1;
        while (n != 0) {
            // 把 n 的二进制位中的最低位的 1 变为 0 之后的结果
            n &= n - 1;
            cnt++;
        }
        return cnt;
    }

    public int reverseBits(int n) {
        int rev = 0;
        for (int i = 0; i < 32 && n != 0; ++i) {
            // 将 n 的最低位与 1 做与运算，得到最低位的值（0或1）
            // 然后将这个值左移 (31 - i) 位，将其放置到 rev 的最高位
            // "|" 是位或运算，用于将得到的位值添加到 rev 中
            rev |= (n & 1) << (31 - i);
            n >>>= 1;
        }
        return rev;
    }

//
//    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
//        PriorityQueue<int[]> pq = new PriorityQueue<>(k, (o1, o2) -> nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]]);
//        List<List<Integer>> ans = new ArrayList<>();
//        int m = nums1.length, n = nums2.length;
//        for (int i = 0; i < Math.min(m, k); i++) {
//            pq.offer(new int[]{i, 0});
//        }
//        while (k-- > 0 && !pq.isEmpty()) {
//            int[] idxPair = pq.poll();
//            List<Integer> list = new ArrayList<>();
//            list.add(nums1[idxPair[0]]);
//            list.add(nums2[idxPair[1]]);
//            ans.add(list);
//            if (idxPair[1] + 1 < n) {
//                pq.offer(new int[]{idxPair[0], idxPair[1] + 1});
//            }
//        }
//
//        return ans;
//
//    }
//
//    public void heapify(List<List<Integer>> nums, int i, int heapSize) {
//        int largest = i;
//        int leftSon = 2 * i + 1, rightSon = 2 * i + 2;
//        int leftV = nums.get(leftSon).get(0) + nums.get(leftSon).get(1);
//        int rightV = nums.get(rightSon).get(0) + nums.get(rightSon).get(1);
//        int largestV = nums.get(largest).get(0) + nums.get(largest).get(1);
//
//        if (leftSon < heapSize && leftV > largestV) largest = leftSon;
//        if (rightSon < heapSize && rightV > largestV) largest = rightSon;
//        if (largest != i) {
//            List<Integer> tmp = nums.get(i);
//            nums.set(i, nums.get(largest));
//            nums.set(largest, tmp);
//        }
//    }
//
//    public int countCompleteDayPairs(int[] hours) {
//        int len = hours.length;
//        int timeCnt;
//        int ans = 0;
//        for (int i = 0; i < len - 1; i++) {
//            timeCnt = hours[i];
//            for (int j = i + 1; j < len; j++) {
//                if ((timeCnt + hours[j]) % 24 == 0) {
//                    ans++;
//                }
//            }
//        }
//        return ans;
//    }
//
//    // 快速排序
//    public void quickSort(int[] nums, int low, int high) {
//        if (low < high) {
//            // 找到基准值的索引
//            int pivotIndex = partition(nums, low, high);
//
//            // 分别对基准值左右两部分进行快速排序
//            quickSort(nums, low, pivotIndex - 1);
//            quickSort(nums, pivotIndex + 1, high);
//        }
//        System.out.println(Arrays.toString(nums));
//    }
//
//    public int partition(int[] nums, int low, int high) {
//        // 最左侧元素作为基准元素
//        int base = nums[low];
//        int i = low, j = high;
//        while (i < j) {
//            while (i < j && nums[j] >= base) j--;
//            while (i < j && nums[i] <= base) i++;
//            // 满足交换规则 交换位置
//            if (i < j) {
//                int temp = nums[i];
//                nums[i] = nums[j];
//                nums[j] = temp;
//            }
//        }
//        // 将基准值放到正确的位置，即 i 指针的当前位置
//        int temp = nums[low];
//        nums[low] = nums[i];
//        nums[i] = temp;
//
//        return i;
//    }
//
//    // 堆排序
//    public void heapSort(int[] nums) {
//        int len = nums.length - 1;
//        // 构架最大堆
//        for (int i = len / 2 - 1; i >= 0; i--) {
//            heapify(nums, i, len);
//        }
//        System.out.println(Arrays.toString(nums));
////        for (int i = len; i >= 0; i--) {
////            // 将首位元素互换，然后进行堆调整
////            int tmp = nums[0];
////            nums[0] = nums[i];
////            nums[i] = tmp;
////            heapify(nums, 0, i);
////        }
//        // 一个个从堆顶取出元素
//        for (int i = len; i >= 0; i--) {
//            // 将当前的根节点移到数组末尾
//            int tmp = nums[0];
//            nums[0] = nums[i];
//            nums[i] = tmp;
//
//            // 调整剩余元素为最大堆 注意此处需要将堆长度-1
//            heapify(nums, 0, i - 1);
//        }
//        System.out.println(Arrays.toString(nums));
//    }
//
//    public void heapify(int[] nums, int i, int heapSize) {
//        int largest = i;
//        // 数组存储情况下，节点i的左右子孩子节点的下标
//        int leftSon = 2 * i + 1, rightSon = 2 * i + 2;
//        if (leftSon <= heapSize && nums[leftSon] > nums[largest]) {
//            largest = leftSon;
//        }
//        if (rightSon <= heapSize && nums[rightSon] > nums[largest]) {
//            largest = rightSon;
//        }
//        // 说明需要调整堆
//        if (largest != i) {
////            int tmp = nums[largest];
////            nums[largest] = nums[i];
////            nums[i] = tmp;
//            swap(nums, largest, i);
//
//            // 递归判断子树是否需要调整
//            heapify(nums, largest, heapSize);
//        }
//    }
//
//    public void swap(int[] nums, int a, int b) {
//        int tmp = nums[a];
//        nums[a] = nums[b];
//        nums[b] = tmp;
//    }
//
//    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
//        int n = profits.length;
//        int curr = 0;
//        int[][] arr = new int[n][2];
//
//        for (int i = 0; i < n; ++i) {
//            arr[i][0] = capital[i];
//            arr[i][1] = profits[i];
//        }
//        Arrays.sort(arr, (a, b) -> a[0] - b[0]);
////        // 封装写法
////        Arrays.sort(arr, Comparator.comparingInt(a -> a[0]));
////        //倒序排序
////        Arrays.sort(arr, (a, b) -> b[0] - a[0]);
//
////        // 链式调用
////        Arrays.sort(students, Comparator.comparingInt((Student s) -> s.age).thenComparing((Student s) -> s.name));
//        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
//        for (int i = 0; i < k; ++i) {
//            // 每一次考虑所有可以投资的情况，使用优先队列选出效益最高的那个
//            while (curr < n && arr[curr][0] <= w) {
//                pq.add(arr[curr][1]);
//                curr++;
//            }
//            if (!pq.isEmpty()) {
//                w += pq.poll();
//            } else {
//                break;
//            }
//        }
//
//        return w;
//    }
//
//    public int findKthLargest(int[] nums, int k) {
//        int heapSize = nums.length - 1;
//        // 建堆
//        for (int i = heapSize / 2 - 1; i >= 0; --i) {
//            maxHeapify(nums, i, heapSize);
//        }
//        // 一个个从堆顶取出元素 （大根堆排序后为增序、小根堆排序完为递减序列）
//        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
//            // 将当前的根节点移到数组末尾
//            int temp = nums[0];
//            nums[0] = nums[i];
//            nums[i] = temp;
//
//            // 此时调整堆的长度应-1
//            --heapSize;
//            maxHeapify(nums, 0, heapSize);
//        }
//        return nums[0];
//    }
//
//    public void maxHeapify(int[] a, int i, int heapSize) {
//        int largest = i;       // 初始化最大元素为根节点
//        int left = 2 * i + 1;   // 左子节点
//        int right = 2 * i + 2;  // 右子节点
//
//        // 如果左子节点大于根节点，则更新最大元素
//        if (left <= heapSize && a[left] > a[largest]) {
//            largest = left;
//        }
//        // 如果右子节点大于当前最大元素，则更新最大元素
//        if (right <= heapSize && a[right] > a[largest]) {
//            largest = right;
//        }
//
//        // 如果最大元素不是根节点，交换它们，并继续调整堆
//        if (largest != i) {
//            int swap = a[i];
//            a[i] = a[largest];
//            a[largest] = swap;
//
//            // 递归地调整影响的子树
//            maxHeapify(a, largest, heapSize);
//        }
//    }
//
//    public int smallestRangeII(int[] nums, int k) {
//        // 先排序变递增
//        Arrays.sort(nums);
//        int len = nums.length;
//        int minNum = nums[0], maxNum = nums[len - 1];
//        int ans = maxNum - minNum;
//        for (int i = 1; i < len; i++) {
//            int mx = Math.max(nums[i - 1] + k, nums[len - 1] - k);
//            int mn = Math.min(nums[0] + k, nums[i] - k);
//            ans = Math.min(ans, mx - mn);
//        }
//        return ans;
//    }
//
//    public int findMin1(int[] nums) {
//        int len = nums.length;
//        int left = 0, right = len - 1;
//        int mid;
//        while (left <= right) {
//            mid = left + (right - left) / 2;
//            if (nums[mid] >= nums[0]) {
//                left = mid + 1;
//            } else {
//                right = mid - 1;
//            }
//        }
//        return nums[left >= len ? 0 : left];
//    }
//
//    public int findMin(int[] nums) {
//        int len = nums.length;
//        int left = 0, right = len - 1;
//        int mid;
//        int minValue = Integer.MAX_VALUE;
//        while (left <= right) {
//            mid = left + (right - left) / 2;
//            if (nums[mid] >= nums[0]) {
//                minValue = Math.min(minValue, nums[0]);
//                left = mid + 1;
//            } else {
//                minValue = Math.min(nums[mid], minValue);
//                right = mid - 1;
//            }
//        }
//        return minValue;
//    }
//
//    public int minOperations(int[] nums) {
//        int len = nums.length;
//        int cnt = 0;
//        for (int i = 0; i < len - 2; i++) {
//            if (nums[i] == 0) {
//                nums[i + 1] = nums[i + 1] == 0 ? 1 : 0;
//                nums[i + 2] = nums[i + 2] == 0 ? 1 : 0;
//                cnt++;
//            }
//        }
//        return nums[len - 1] != 1 || nums[len - 2] != 1 ? -1 : cnt;
//    }
//
//
//    public int[] twoSum2(int[] nums, int target) {
//        HashMap<Integer, Integer> helper = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            if (helper.containsKey(target - nums[i])) {
//                return new int[]{helper.get(target - nums[i]), i};
//            } else {
//                helper.put(nums[i], i);
//            }
//        }
//        return null;
//    }
//
//    public int search(int[] nums, int target) {
//        int len = nums.length;
//        if (len == 1) return nums[0] == target ? 0 : -1;
//        int left = 0, right = len - 1;
//        int mid;
//        while (left <= right) {
//            // 防止由于left + right超出定义类型（如int、Long）的最大值而导致内存溢出。
////            mid = left + (right - left) >> 1; // 与下面的写法作用相同，只是实现方式不同。 通常位运算更快
//            mid = left + (right - left) / 2;
//            if (nums[mid] == target) return mid;
//            if (nums[0] <= nums[mid]) {
//                if (nums[0] <= target && target < nums[mid]) {
//                    right = mid - 1;
//                } else {
//                    left = mid + 1;
//                }
//            } else {
//                if (nums[mid] < target && target <= nums[len - 1]) {
//                    left = mid + 1;
//                } else {
//                    right = mid - 1;
//                }
//            }
//        }
//        return -1;
//    }
//
//    public int searchHelper(int[] nums, int target, boolean flag) {
//        int len = nums.length;
//        int left = 0, right = len - 1;
//        int mid;
//        while (left <= right) {
//            mid = left + (right - left) / 2;
//            if (flag) {
//                if (nums[mid] < target) {
//                    left = mid + 1;
//                } else {
//                    right = mid - 1;
//                }
//            } else {
//                if (nums[mid] < target) {
//                    right = mid - 1;
//                } else {
//                    left = mid + 1;
//                }
//            }
//
//        }
//        return left;
//    }
//
//
//    public double minimumAverage(int[] nums) {
//        int len = nums.length;
//        int left = 0, right = len - 1;
//        double minAverage = Double.MAX_VALUE;
//        // sort first
//        Arrays.sort(nums);
//        while (left < right) {
////            minAverage = Math.min(minAverage, countBetween(nums, left, right));
//            minAverage = Math.min(minAverage, (double) (nums[left] + nums[right]) / 2);
//            left++;
//            right--;
//        }
//        return minAverage;
//    }
//
//    public int countBetween(int[] nums, int head, int end) {
//        int cnt = 0;
//        for (int i = head; i <= end; i++) {
//            cnt += nums[i];
//        }
//        return cnt;
//    }
//
//    public int findPeakElement(int[] nums) {
//        int left = 0;
//        // 一定不是最后一个元素
//        int right = nums.length - 2;
//        while (left <= right) {
//            int mid = left + (right - left) / 2;
//            // if (nums[mid] > nums[mid + 1]) {
//            //     right = mid - 1;
//            // } else {
//            //     left = mid + 1;
//            // }
//            // 从左逼近
//            if (nums[mid] < nums[mid + 1]) {
//                left = mid + 1;
//            } else {
//                right = mid - 1;
//            }
//        }
//        return left;
//    }
//
//    public int maxHeightOfTriangle(int red, int blue) {
//        return Math.max(mightHigh(red, blue, true), mightHigh(red, blue, false));
//    }
//
//    public int mightHigh(int red, int blue, boolean redFirst) {
//        int high = 1;
//        // 此处的redFirst是为了应对示例四！ 在||的情况下保证一方不满足即退出循环
//        while (redFirst && red >= high || !redFirst && blue >= high) {
//            if (redFirst) {
//                red -= high;
//            } else {
//                blue -= high;
//            }
//            high++;
//            redFirst = !redFirst;
//        }
//        return high - 1;
//    }
//
//    public int maxHeightOfTriangle1(int red, int blue) {
//        int odd = 2 * (int) (Math.sqrt(red)) - 1;
//        int even = 2 * (int) ((-1 + Math.sqrt(1 + 4 * blue)) / 2);
//
//        int odd1 = 2 * (int) (Math.sqrt(blue)) - 1;
//        int even1 = 2 * (int) ((-1 + Math.sqrt(1 + 4 * red)) / 2);
//        return Math.max(Math.min(odd, even) + 1, Math.min(odd1, even1) + 1);
//    }
//
//
//    public boolean searchMatrix(int[][] matrix, int target) {
//        int row = matrix.length, column = matrix[0].length;
//        int left = 0, right = row * column - 1;
//        int mid, tmp;
//        while (left <= right) {
//            mid = left + (right - left) / 2;
//            tmp = matrix[mid / column][mid % column];
//            if (tmp < target) left = mid + 1;
//            else if (tmp > target) right = mid - 1;
//            else return true;
//        }
//        System.out.println(left);
//        System.out.println(right);
//        System.out.println(row);
//        System.out.println(column);
//        return false;
//    }
//
//    //    public int[] searchRange(int[] nums, int target) {
////        int len = nums.length;
////        if (len == 0) return new int[]{-1, -1};
////        int leftAns = binarySearch(nums, target, true);
////        int rightAns = binarySearch(nums, target, false);
////        int[] ans = new int[]{leftAns, rightAns};
////        if (ans[0] >= len || nums[ans[0]] != target) return new int[]{-1, -1};
////        return ans;
////    }
//    public int[] searchRange(int[] nums, int target) {
//        int len = nums.length;
//        if (len == 0) return new int[]{-1, -1};
//        int leftAns = binarySearch(nums, target, false);
//        int rightAns = binarySearch(nums, target, true);
//        int[] ans = new int[]{leftAns, rightAns};
//        // 如果存在，那么一定满足 leftAns <= rightAns
//        if (ans[0] > ans[1]) return new int[]{-1, -1};
////        if (ans[0] > len || nums[ans[0]] != target) return new int[]{-1, -1};
//        return ans;
//    }
//
//    public int binarySearch(int[] nums, int target, boolean flag) {
//        int left = 0, right = nums.length - 1;
//        int mid;
//        while (left <= right) {
//            mid = left + (right - left) / 2;
//            if (nums[mid] < target || flag && nums[mid] <= target) {
//                left = mid + 1;
//            } else {
//                right = mid - 1;
//            }
//        }
//        return flag ? left : right;
//    }
//
////    public int[] searchRange(int[] nums, int target) {
////        int len = nums.length;
////        if (len == 0) return new int[]{-1, -1};
////        int[] ans = new int[2];
////        int left = 0, right = len - 1;
////        int mid;
////        // 找到第一个出现的位置
////        while (left <= right) {
////            mid = left + (right - left) / 2;
////            if (nums[mid] < target) left = mid + 1;
////            else right = mid - 1;
////        }
////        // 是否越界 或 是否存在target元素
////        if (left < len && nums[left] == target) ans[0] = left;
////        else return new int[]{-1, -1};
////        // 重新初始化
////        left = 0;
////        right = len - 1;
////        // 找到最后一个出现的位置
////        while (left <= right) {
////            mid = left + (right - left) / 2;
////            if (nums[mid] <= target) left = mid + 1;
////            else right = mid - 1;
////        }
////        ans[1] = right;
////        return ans;
////    }
//
//    public int searchInsert(int[] nums, int target) {
//        int left = -1, right = nums.length;
//        int mid;
//        while (left + 1 < right) {
//            mid = left + (right - left) / 2;
//            if (nums[mid] < target) {
//                left = mid;
//            } else {
//                right = mid;
//            }
//        }
//        return right;
//    }
//
//    /**
//     * 根据if的判断条件:
//     * left左边的值一直保持小于target，right右边的值一直保持大于等于target.
//     * 而且left最终一定等于right+1，这么一来，循环结束后，在left和right之间画一条竖线，恰好可以把数组分为两部分:
//     * left左边的部分和right右边的部分，而且left左边的部分全部小于target,并以right结尾；
//     * right右边的部分全部大于等于target，并以left为首。所以最终答案一定在left的位置。
//     */
//    public int searchInsert1(int[] nums, int target) {
//        int len = nums.length;
//        int left = 0, right = len - 1;
//        int mid;
//        while (left <= right) {
//            mid = (left + right) >> 1;
//            if (nums[mid] <= target) {
//                left = mid + 1;
//            } else {
//                right = mid - 1;
//            }
//        }
//        System.out.println(left);
//        System.out.println(right);
//        return nums[right] == target ? right : left;
//    }
//
//    public int searchInsert2(int[] nums, int target) {
//        int left = -1, right = nums.length;
//        int mid;
//        while (left + 1 < right) {
//            mid = left + (right - left) / 2;
//            if (nums[mid] < target) {
//                left = mid;
//            } else {
//                right = mid;
//            }
//        }
//        return right;
//    }
//
//    public int twoEggDrop(int n) {
//        int[] f = new int[n + 1];
//        Arrays.fill(f, Integer.MAX_VALUE / 2);
//        f[0] = 0;
//        for (int i = 1; i <= n; i++) {
//            for (int k = 1; k <= i; k++) {
//                f[i] = Math.min(f[i], Math.max(k - 1, f[i - k]) + 1);
//            }
//        }
//        return f[n];
//    }
//
//    public int duplicateNumbersXOR(int[] nums) {
//        int ans = 0;
//        HashMap<Integer, Integer> helper = new HashMap<>();
//        for (int num : nums) {
//            if (helper.containsKey(num)) {
//                ans ^= num;
//            } else {
//                helper.put(num, 1);
//            }
//        }
//        return ans;
//    }
//
//    public int maxSubarraySumCircular(int[] nums) {
//        int n = nums.length;
//        int preMax = nums[0], maxRes = nums[0];
//        int preMin = nums[0], minRes = nums[0];
//        int sum = nums[0];
//        for (int i = 1; i < n; i++) {
//            preMax = Math.max(preMax + nums[i], nums[i]);
//            maxRes = Math.max(maxRes, preMax);
//            preMin = Math.min(preMin + nums[i], nums[i]);
//            minRes = Math.min(minRes, preMin);
//            sum += nums[i];
//        }
//        return maxRes < 0 ? maxRes : Math.max(maxRes, sum - minRes);
//    }
//
//
//    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
//        Map<Integer, Integer> count = new HashMap<>();
//        Map<Integer, Integer> count2 = new HashMap<>();
//        int max1 = 0;
//        for (int num : nums1) {
//            count.put(num, count.getOrDefault(num, 0) + 1);
//            max1 = Math.max(max1, num);
//        }
//        for (int num : nums2) {
//            count2.put(num, count2.getOrDefault(num, 0) + 1);
//        }
//        long res = 0;
//        for (int a : count2.keySet()) {
//            for (int b = a * k; b <= max1; b += a * k) {
//                if (count.containsKey(b)) {
//                    res += (long) count.get(b) * count2.get(a);
//                }
//            }
//        }
//        return res;
//    }
//
//
//    public int maxSubArray(int[] nums) {
//        int res = nums[0];
//        for (int i = 1; i < nums.length; i++) {
//            nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
//            res = Math.max(res, nums[i]);
//        }
//        return res;
//    }
//
//    public int minimumDifference(int[] nums, int k) {
//        int ans = Integer.MAX_VALUE;
//        for (int i = 0; i < nums.length; i++) {
//            int x = nums[i];
//            // 单个元素也算子数组
//            ans = Math.min(ans, Math.abs(x - k));
//            for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j--) {
//                // 现在 nums[j] = 原数组 nums[j] 到 nums[i] 的 OR
//                nums[j] |= x;
//                ans = Math.min(ans, Math.abs(nums[j] - k));
//            }
//        }
//        return ans;
//    }
//
//    public ListNode sortList(ListNode head) {
//        if (head == null || head.next == null) return head;
//        ListNode fast = head.next, slow = head;
//        // 找到链表的中点
//        while (fast != null && fast.next != null) {
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//        // 后半段
//        ListNode mid = slow.next;
//        // 前半段
//        slow.next = null;
//        // 递归调用  归并排序利用了递归
//        return merge(sortList(head), sortList(mid));
//    }
//
//    public ListNode merge(ListNode left, ListNode right) {
//        // 最新头节点
//        ListNode node = new ListNode(0);
//        ListNode res = node;
//        while (left != null && right != null) {
//            if (left.val < right.val) {
//                res.next = left;
//                left = left.next;
//            } else {
//                res.next = right;
//                right = right.next;
//            }
//            res = res.next;
//        }
//        res.next = left != null ? left : right;
//
//        return node.next;
//    }
//
//
//    public String destCity(List<List<String>> paths) {
//        HashSet<String> helper = new HashSet<>();
//        for (List<String> path : paths) {
//            helper.add(path.get(0));
//        }
//        for (List<String> path : paths) {
//            if (!helper.contains(path.get(1)))
//                return path.get(1);
//        }
//        return null;
//    }
//
////    public ListNode sortList(ListNode head) {
////        ListNode p = head;
////        ListNode helperP = new ListNode(-1);
////        ListNode newHead = helperP;
////
////        List<Integer> helper = new ArrayList<>();
////        while (p != null) {
////            helper.add(p.val);
////            p = p.next;
////        }
////        Collections.sort(helper);
////        int i = 0;
////        while (i < helper.size()) {
////            helperP.next = new ListNode(helper.get(i++));
////            helperP = helperP.next;
////        }
////        return newHead;
////    }
//
//    public int minSpeedOnTime(int[] dist, double hour) {
//        int len = dist.length;
//        // 将 hour 乘 100 以转为整数
//        long hr = Math.round(hour * 100);
//        if (hour <= len - 1) return -1;
//
//        // 二分
//        int l = 1;
//        int r = 10000000;
//
//        while (l < r) {
//            int mid = l + (r - l) / 2;
//            // 判断当前时速是否满足时限
//            long t = 0;
//            // 前 n-1 段中第 i 段贡献的时间： ceil(dist[i] / mid)
//            for (int i = 0; i < len - 1; ++i) {
//                t += (long) Math.ceil((double) dist[i] / mid);
//            }
//            // 前n-1段的距离 + 第n-1段的距离
//            long distance = t * mid + dist[len - 1];
//            if (distance * 100 <= hr * mid) { // 通分以转化为整数比较
//                r = mid;
//            } else {
//                l = mid + 1;
//            }
//        }
//        return l;
//    }
//
//    public int mincostTickets(int[] days, int[] costs) {
//        int lastDay = days[days.length - 1];
//        boolean[] isTravel = new boolean[lastDay + 1];
//        for (int d : days) {
//            isTravel[d] = true;
//        }
//        int[] memo = new int[lastDay + 1];
//        return dfs(lastDay, isTravel, costs, memo);
//    }
//
//    private int dfs(int i, boolean[] isTravel, int[] costs, int[] memo) {
//        if (i <= 0) {
//            return 0;
//        }
//        if (memo[i] > 0) { // 之前计算过
//            return memo[i];
//        }
//        if (!isTravel[i]) {
//            return memo[i] = dfs(i - 1, isTravel, costs, memo);
//        }
//        return memo[i] = Math.min(dfs(i - 1, isTravel, costs, memo) + costs[0],
//                Math.min(dfs(i - 7, isTravel, costs, memo) + costs[1],
//                        dfs(i - 30, isTravel, costs, memo) + costs[2]));
//    }
//
//    public TreeNode sortedArrayToBST(int[] nums) {
//        //每次将中点作为根节点，其左边的所有元素作为左子树，右边的所有元素作为右子树
//        if (nums.length == 0) {
//            return null;
//        }
//        int mid = nums.length / 2;
//        TreeNode root = new TreeNode(nums[mid]);
//        root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid));
//        root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid + 1, nums.length));
//        return root;
//    }
//
//
//    public int timeRequiredToBuy(int[] tickets, int k) {
//        int res = 0, tmp = tickets[k];
//        for (int i = 0; i < tickets.length; i++) {
//            if (i <= k) {
//                res += Math.min(tickets[i], tmp);
//            } else {
//                if (tickets[i] >= tmp) res += tmp - 1;
//                else res += tickets[i];
//            }
//        }
//        return res;
//    }
//
//    public boolean exist(char[][] board, String word) {
//        for (int i = 0; i < board.length; i++) {
//            for (int j = 0; j < board[0].length; j++) {
//                if (board[i][j] == word.charAt(0)) {
//                    if (existDFS(board, word, i, j, 0)) return true;
//                }
//            }
//        }
//        return false;
//    }
//
//    public boolean existDFS(char[][] board, String word, int r, int c, int cur) {
//
//        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != word.charAt(cur))
//            return false;
//        if (cur == word.length() - 1)
//            return true;
//        // 标记已被访问过的位置
//        board[r][c] = '1';
//        boolean res =
//                existDFS(board, word, r + 1, c, cur + 1) ||
//                        existDFS(board, word, r, c + 1, cur + 1) ||
//                        existDFS(board, word, r - 1, c, cur + 1) ||
//                        existDFS(board, word, r, c - 1, cur + 1);
//        // 复原
//        board[r][c] = word.charAt(cur);
//        return res;
//    }
//
//    public List<String> generateParenthesis(int n) {
//        List<String> ansString = new ArrayList<>();
//        generateParenthesisDFS(ansString, new StringBuilder(), n, 0, 0);
//        return ansString;
//    }
//
//    public void generateParenthesisDFS(List<String> ansString, StringBuilder str, int n, int cntL, int cntR) {
//        if (str.length() == 2 * n) {
//            ansString.add(str.toString());
//            return;
//        }
//        if (cntL < n) {
//            str.append('(');
//            generateParenthesisDFS(ansString, str, n, cntL + 1, cntR);
//            str.deleteCharAt(str.length() - 1);
//        }
//        if (cntR < cntL) {
//            str.append(')');
//            generateParenthesisDFS(ansString, str, n, cntL, cntR + 1);
//            str.deleteCharAt(str.length() - 1);
//        }
//    }
//
//    public int totalNQueens(int n) {
//        Set<Integer> columns = new HashSet<>();
//        Set<Integer> diagonals1 = new HashSet<>();
//        Set<Integer> diagonals2 = new HashSet<>();
//        return backtrack(n, 0, columns, diagonals1, diagonals2);
//    }
//
//    public int backtrack(int n, int row, Set<
//            Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
//        if (row == n) {
//            return 1;
//        } else {
//            int count = 0;
//            for (int i = 0; i < n; i++) {
//                int diagonal1 = row - i, diagonal2 = row + i;
//                if (columns.contains(i) || diagonals1.contains(diagonal1) || diagonals2.contains(diagonal2)) {
//                    continue;
//                }
//                // 在集合中记录当前下标位置
//                columns.add(i);
//                diagonals1.add(diagonal1);
//                diagonals2.add(diagonal2);
//                // 递归求可行解
//                count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
//                columns.remove(i);
//                diagonals1.remove(diagonal1);
//                diagonals2.remove(diagonal2);
//            }
//            return count;
//        }
//    }
//
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        List<List<Integer>> ans = new ArrayList<>();
//        List<Integer> midAns = new ArrayList<>();
//        combinationSumDFS(ans, midAns, 0, target, candidates);
//        return ans;
//    }
//
//    public void combinationSumDFS(List<List<Integer>> ans, List<Integer> midAns, int index, int target,
//                                  int[] candidates) {
//        if (target == 0) {
//            ans.add(new ArrayList<>(midAns));
//            return;
//        }
//        for (int i = index; i < candidates.length; i++) {
//            if (candidates[i] <= target) {
//                midAns.add(candidates[i]);
//                combinationSumDFS(ans, midAns, i, target - candidates[i], candidates);
//                midAns.remove(midAns.size() - 1);
//            }
//        }
//
//    }
//
//    public int takeCharacters(String s, int k) {
//        int[] cnt = new int[3];
//        int len = s.length();
//        int ans = len;
//        // 对各字符计数
//        for (int i = 0; i < len; i++) {
//            cnt[s.charAt(i) - 'a']++;
//        }
//        if (cnt[0] >= k && cnt[1] >= k && cnt[2] >= k) {
//            ans = Math.min(ans, len);
//        } else {
//            return -1;
//        }
//
//        int l = 0;
//        for (int r = 0; r < len; r++) {
//            cnt[s.charAt(r) - 'a']--;
//            while (l < r && (cnt[0] < k || cnt[1] < k || cnt[2] < k)) {
//                cnt[s.charAt(l) - 'a']++;
//                l++;
//            }
//            if (cnt[0] >= k && cnt[1] >= k && cnt[2] >= k) {
//                ans = Math.min(ans, len - (r - l + 1));
//            }
//        }
//
//        return ans;
//
//    }
//
//    public List<List<Integer>> permute(int[] nums) {
//        List<List<Integer>> ans = new ArrayList<>();
//        List<Integer> midHelper = new ArrayList<>();
//        int len = nums.length;
//        boolean[] visited = new boolean[len];
//        permuteDFS(midHelper, ans, 0, len, visited, nums);
//        return ans;
//    }
//
//    public void permuteDFS(List<Integer> midHelper, List<List<Integer>> ans, int cnt, int len,
//                           boolean[] visited, int[] nums) {
//        if (cnt == len) {
//            ans.add(new ArrayList<>(midHelper));
//        }
//        for (int i = 0; i < len; i++) {
//            // 标记已访问过的元素
//            if (visited[i]) continue;
//            visited[i] = true;
//            midHelper.add(nums[i]);
//            permuteDFS(midHelper, ans, cnt + 1, len, visited, nums);
//            midHelper.remove(midHelper.size() - 1);
//            visited[i] = false;
//        }
//    }
//
//    public int differenceOfSum(int[] nums) {
//        int allNumCnt = 0, allCnt = 0;
//        for (int num : nums) {
//            allNumCnt += eachNumCnt(num);
//            allCnt += num;
//        }
//        return Math.abs(allCnt - allNumCnt);
//    }
//
//    public int eachNumCnt(int num) {
//        int cnt = 0;
//        while (num != 0) {
//            cnt += num % 10;
//            num /= 10;
//        }
//        return cnt;
//    }
//
//    List<List<Integer>> seqCnt = new ArrayList<>();
//    List<Integer> midHelper = new ArrayList<>();
//
//    public List<List<Integer>> combine(int n, int k) {
//
//        seqDfs(1, n, k);
//        return seqCnt;
//    }
//
//    public void seqDfs(int cur, int n, int k) {
//        if (k == 0) {
//            seqCnt.add(new ArrayList<>(midHelper));
//        }
//        for (int i = cur; i <= n; i++) {
//            midHelper.add(i);
//            seqDfs(i + 1, n, k - 1);
//            midHelper.remove(midHelper.size() - 1);
//        }
//    }
//
////    public void seqDfs(int cur, int n, int k) {
////        // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
////        if (midHelper.size() + (n - cur + 1) < k) {
////            return;
////        }
////        // 记录合法的答案
////        if (midHelper.size() == k) {
////            seqCnt.add(new ArrayList<>(midHelper));
////            return;
////        }
////        // 考虑选择当前位置
////        midHelper.add(cur);
////        seqDfs(cur + 1, n, k);
////        midHelper.remove(midHelper.size() - 1);
////        // 考虑不选择当前位置
////        seqDfs(cur + 1, n, k);
////    }
//
//    public List<String> letterCombinations(String digits) {
//        List<String> ans = new ArrayList<>();
//        if (digits.isEmpty()) return ans;
//        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
//            put('2', "abc");
//            put('3', "def");
//            put('4', "ghi");
//            put('5', "jkl");
//            put('6', "mno");
//            put('7', "pqrs");
//            put('8', "tuv");
//            put('9', "wxyz");
//        }};
//        backtrack(ans, phoneMap, digits, 0, new StringBuffer());
//        return ans;
//    }
//
//    public void backtrack(List<String> ans, Map<Character, String> phoneMap, String digits,
//                          int index, StringBuffer tmp) {
//        if (index == digits.length()) {
//            ans.add(tmp.toString());
//        } else {
//            char digit = digits.charAt(index);
//            String letters = phoneMap.get(digit);
//            int lettersCount = letters.length();
//            for (int i = 0; i < lettersCount; i++) {
//                tmp.append(letters.charAt(i));
//                backtrack(ans, phoneMap, digits, index + 1, tmp);
//                tmp.deleteCharAt(index);
//            }
//        }
//    }
//
//
//    public long maximumSubsequenceCount(String text, String pattern) {
//        long ansCnt = 0;
//        boolean flag = pattern.charAt(0) == pattern.charAt(1);
//        Deque<Character> queue = new LinkedList<>();
//        int leftCnt = 0, rightCnt = 0, len = text.length();
//        for (int i = 0; i < len; i++) {
//            char tmp = text.charAt(i), pattern0 = pattern.charAt(0), pattern1 = pattern.charAt(1);
//            // 将待处理的字符入队 并记录个数
//            if (tmp == pattern1) {
//                queue.offerLast(tmp);
//                rightCnt++;
//            } else if (tmp == pattern0) {
//                queue.offerLast(tmp);
//                leftCnt++;
//            }
//        }
//        int maybeMax = Math.max(leftCnt, rightCnt);
//        while (!queue.isEmpty()) {
//            char tmp = queue.pollFirst();
//            if (tmp == pattern.charAt(0) || (flag && tmp == pattern.charAt(0))) {
//                leftCnt--;
//                ansCnt += rightCnt;
//            } else rightCnt--;
//        }
//        return flag ? (ansCnt + maybeMax) / 2 : ansCnt + maybeMax;
//    }
//
//    public int minMutation(String startGene, String endGene, String[] bank) {
//
//        Set<String> visited = new HashSet<>();
//        char[] keys = {'A', 'C', 'G', 'T'};
//        Set<String> cnt = new HashSet<>(Arrays.asList(bank));
//        // 特殊情况处理
//        if (startGene.equals(endGene)) return 0;
//        if (!cnt.contains(endGene)) return -1;
//
//        Queue<String> queue = new ArrayDeque<>();
//        queue.offer(startGene);
//        visited.add(startGene);
//        int step = 1;
//        while (!queue.isEmpty()) {
//            int size = queue.size();
//            for (int i = 0; i < size; i++) {
//                String curr = queue.poll();
//                // 尝试所有可能的变化后的基因 最多可能会生成 3×8=24 种不同的基因序列。
//                for (int j = 0; j < 8; j++) {
//                    for (int k = 0; k < 4; k++) {
//                        if (keys[k] != curr.charAt(j)) {
//                            StringBuilder sb = new StringBuilder(curr);
//                            sb.setCharAt(j, keys[k]);
//                            String next = sb.toString();
//                            if (!visited.contains(next) && cnt.contains(next)) {
//                                if (next.equals(endGene)) {
//                                    return step;
//                                }
//                                queue.offer(next);
//                                visited.add(next);
//                            }
//                        }
//                    }
//                }
//            }
//            step++;
//        }
//        return -1;
//
//    }
//
//    public int snakesAndLadders(int[][] board) {
//        int n = board.length;
//        boolean[] vis = new boolean[n * n + 1];
//        Queue<int[]> queue = new LinkedList<>();
//        // {所在格子序号，移动次数}
//        queue.offer(new int[]{1, 0});
//        while (!queue.isEmpty()) {
//            int[] p = queue.poll();
//            // 可移动范围（骰子）
//            for (int i = 1; i <= 6; ++i) {
//                int nxt = p[0] + i;
//                // 超出边界
//                if (nxt > n * n) break;
//                // 得到下一步的行列
//                int[] rc = id2rc(nxt, n);
//                // 存在蛇或梯子
//                if (board[rc[0]][rc[1]] > 0) nxt = board[rc[0]][rc[1]];
//                // 到达终点
//                if (nxt == n * n) return p[1] + 1;
//                if (!vis[nxt]) {
//                    vis[nxt] = true;
//                    // 扩展新状态
//                    queue.offer(new int[]{nxt, p[1] + 1});
//                }
//            }
//        }
//        return -1;
//    }
//
//    public int[] id2rc(int id, int n) {
//        int r = (id - 1) / n, c = (id - 1) % n;
//        if (r % 2 == 1) {
//            c = n - 1 - c;
//        }
//        return new int[]{n - 1 - r, c};
//    }
//
//    public int maxScoreSightseeingPair(int[] values) {
//        int ans = 0, len = values.length, mx = values[0] + 0;
//        // 用以标识是否为第一次进入循环
//        for (int j = 1; j < len; j++) {
//            ans = Math.max(ans, mx + values[j] - j);
//            mx = Math.max(mx, values[j] + j);
//        }
//        return ans;
//    }
//
//    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
//        int left = 0;
//        int right = 0;
//
//        for (int time : workerTimes) {
//            right = Math.max(right, time * mountainHeight * (mountainHeight + 1) / 2);
//        }
//
//        while (left < right) {
//            int mid = (left + right) / 2;
//            if (canFinishWithinTime(mid, mountainHeight, workerTimes)) {
//                right = mid;
//            } else {
//                left = mid + 1;
//            }
//        }
//        return left;
//    }
//
//    private static boolean canFinishWithinTime(int mid, int mountainHeight, int[] workerTimes) {
//        int totalHeightReduced = 0;
//
//        for (int time : workerTimes) {
//            int x = (int) ((-1 + Math.sqrt(1 + (double) (8L * mid) / time)) / 2);
//            totalHeightReduced += x;
//        }
//        return totalHeightReduced >= mountainHeight;
//    }
//
//
//    public boolean reportSpam(String[] message, String[] bannedWords) {
//        HashMap<String, Integer> helper = new HashMap<>();
//        int cnt = 0;
//        for (String bannedWord : bannedWords) {
//            helper.put(bannedWord, 1);
//        }
//        for (String s : message) {
//            if (helper.containsKey(s)) cnt++;
//        }
//        return cnt >= 2;
//    }
//
//
//    public int findJudge(int n, int[][] trust) {
//        int[] inDegrees = new int[n + 1];
//        int[] outDegrees = new int[n + 1];
//        for (int[] edge : trust) {
//            int x = edge[0], y = edge[1];
//            inDegrees[y]++;
//            outDegrees[x]++;
//        }
//        for (int i = 1; i <= n; ++i) {
//            if (inDegrees[i] == n - 1 && outDegrees[i] == 0) {
//                return i;
//            }
//        }
//        return -1;
//    }
//
//
//    public int[] getSneakyNumbers(int[] nums) {
//        List<Integer> ans = new ArrayList<>();
//
//        int[] helper = new int[nums.length];
//        for (int num : nums) {
//            helper[num]++;
//            if (helper[num] == 2) ans.add(num);
//        }
//        return ans.stream().mapToInt(Integer::intValue).toArray();
//    }
//
//    public int edgeScore(int[] edges) {
//        long maxValue = 0;
//        int ansPos = 0;
//        long[] helper = new long[edges.length];
//        for (int i = 0; i < edges.length; i++) {
//            int tmp = edges[i];
//            helper[tmp] += i;
//            if (helper[tmp] > helper[ansPos] || (helper[tmp] == helper[ansPos] && tmp < ansPos)) {
//                ansPos = tmp;
//            }
//        }
////        for (int i = 0; i < edges.length; i++) {
////            if (helper[i] > maxValue) {
////                maxValue = helper[i];
////                ansPos = i;
////            }
////        }
//        return ansPos;
//    }
//
//    public int[] findOrder(int numCourses, int[][] prerequisites) {
//        List<List<Integer>> helper = new ArrayList<>();
//        for (int i = 0; i < numCourses; i++) {
//            helper.add(new ArrayList<>());
//        }
//        System.out.println(helper);
//        int[] inDegree = new int[numCourses];
////        List<Integer> ans = new ArrayList<>();
//        int[] ans = new int[numCourses];
//        int flag = 0;
//        for (int[] prerequisite : prerequisites) {
//            helper.get(prerequisite[1]).add(prerequisite[0]);
//            inDegree[prerequisite[0]]++;
//        }
//        Deque<Integer> queue = new LinkedList<>();
//        for (int i = 0; i < numCourses; i++) {
//            if (inDegree[i] == 0) queue.offerLast(i);
//        }
//        // 初始状态即为死循环
//        if (queue.isEmpty()) return new int[0];
//        while (!queue.isEmpty()) {
//            int course = queue.pollFirst();
////            ans.add(course);
//            ans[flag++] = course;
//            for (int pre : helper.get(course)) {
//                inDegree[pre]--;
//                if (inDegree[pre] == 0) queue.offerLast(pre);
//            }
//        }
//        return flag == numCourses ? ans : new int[0];
////        return ans.size() == numCourses ? ans.stream().mapToInt(Integer::intValue).toArray() : new int[0];
//    }
//
//    HashMap<Integer, Integer> helper;
//
//    public int countSpecialNumbers(int n) {
//        int ans = 0;
//        for (int i = 1; i <= n; i++) {
//            if (isSpecialNumber(i)) ans++;
//        }
//        return ans;
//    }
//
//    public boolean isSpecialNumber(int num) {
//        helper = new HashMap<>();
//        int p;
//        while (num != 0) {
//            p = num % 10;
//            num /= 10;
//            if (helper.containsKey(p)) return false;
//            else helper.put(p, 1);
//        }
//        return true;
//    }
//
//    public boolean canFinish(int numCourses, int[][] prerequisites) {
//        // 建立图和入度表
//        List<List<Integer>> graph = new ArrayList<>();
//        for (int i = 0; i < numCourses; i++) {
//            graph.add(new ArrayList<>());
//        }
//        // 记录每个课程的入度数 即 先修课程数量
//        int[] indegrees = new int[numCourses];
//        for (int[] pre : prerequisites) {
//            graph.get(pre[1]).add(pre[0]);
//            indegrees[pre[0]]++;
//        }
//        // 使用队列进行拓扑排序
//        // 将所有入度为0的顶点（没有先修课程的课程）放入队列中
//        Queue<Integer> queue = new LinkedList<>();
//        for (int i = 0; i < numCourses; i++) {
//            if (indegrees[i] == 0) queue.offer(i);
//        }
//        int coursesFinished = 0;
//        while (!queue.isEmpty()) {
//            // 出队代表完成该课程
//            int course = queue.poll();
//            coursesFinished++;
//            // 将该课程作为先修课程的课程入度 - 1
//            for (int pre : graph.get(course)) {
//                indegrees[pre]--;
//                // 当入度为0 即先修课程全部完成时 入队
//                if (indegrees[pre] == 0) queue.offer(pre);
//            }
//        }
//        // 如果完成的课程数量等于总课程数量，则没有环，可以完成所有课程
//        return coursesFinished == numCourses;
//    }
//
//    //        Scanner scanner = new Scanner(System.in);
////        // 记录0的个数
////        int zeroNum = 0;
////        // 程序运行控制码
////        String code = "C";
////        // 每次的随机数组下标 以及 牌九大小
////        int randomIndex, randomNum;
////        String[] paiJiuType = {
////                "二尿幺1", "二尿幺2", "喝三儿~", "板凳四1", "板凳四2", "飞四1", "飞四2",
////                "红五", "黑五", "喝六儿~", "梭六儿1", "梭六儿2", "铜锤六儿1", "铜锤六儿2",
////                "人七1", "人七2", "黑七", "红七", "血八1", "血八2", "二六八", "三五八",
////                "红九", "黑九", "红十1", "红十2", "花十1", "花十2", "虎子1", "虎子2", "老千！1", "老千！2"};
////        int[] paiJiu = {
////                2, 2, 3, 41, 41, 42, 42, 51,
////                52, 61, 62, 62, 63, 63,
////                71, 71, 72, 73, 81, 81, 82, 83, 91, 92, 101, 101, 102, 102, 11, 11, 12, 12};
//////        int[] paiJiuTmp = paiJiu;
////        while ("C".equals(code)) {
////            Random random = new Random();
////            randomIndex = random.nextInt(paiJiu.length - zeroNum);
////            //根据现有大小获取随机值
////            randomNum = paiJiu[randomIndex];
////            if (randomNum > 12) {
////                randomNum = randomNum / 10;
////            }
////            System.out.println("牌九点数为：" + randomNum);
////            System.out.println("牌九种类为：" + paiJiuType[randomIndex]);
//////            paiJiu[randomIndex] = 0;
////            zeroNum++;
////            if (zeroNum == paiJiu.length) break;
////            // 交换首尾元素位置--both 点数数组和类型数组
////            int tmpNum = paiJiu[randomIndex];
////            paiJiu[randomIndex] = paiJiu[paiJiu.length - zeroNum];
////            paiJiu[paiJiu.length - zeroNum] = tmpNum;
////
////            String tmpTpye = paiJiuType[randomIndex];
////            paiJiuType[randomIndex] = paiJiuType[paiJiuType.length - zeroNum];
////            paiJiuType[paiJiuType.length - zeroNum] = tmpTpye;
////
////
//////            System.out.println(zeroNum + 1);
////            // 获取下次程序运行码
////            code = scanner.nextLine().toUpperCase();
////        }
//    public int longestContinuousSubstring(String s) {
//        int longestLength = 1, length = s.length(), tmp = 1;
//        for (int i = 1; i < length; i++) {
//            if (s.charAt(i) - s.charAt(i - 1) == 1) tmp += 1;
//            else {
//                longestLength = Math.max(longestLength, tmp);
//                tmp = 1;
//            }
//        }
//        longestLength = Math.max(longestLength, tmp);
//        return longestLength;
//    }
//
//    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
//        Arrays.sort(buses);
//        Arrays.sort(passengers);
//        int pos = 0;
//        int space = 0;
//
//        for (int arrive : buses) {
//            space = capacity;
//            while (space > 0 && pos < passengers.length && passengers[pos] <= arrive) {
//                space--;
//                pos++;
//            }
//        }
//
//        pos--;
//        int lastCatchTime = space > 0 ? buses[buses.length - 1] : passengers[pos];
//        while (pos >= 0 && passengers[pos] == lastCatchTime) {
//            pos--;
//            lastCatchTime--;
//        }
//
//        return lastCatchTime;
//    }
//
//    class Node {
//        public int val;
//        public List<Node> neighbors;
//
//        public Node() {
//            val = 0;
//            neighbors = new ArrayList<Node>();
//        }
//
//        public Node(int _val) {
//            val = _val;
//            neighbors = new ArrayList<Node>();
//        }
//
//        public Node(int _val, ArrayList<Node> _neighbors) {
//            val = _val;
//            neighbors = _neighbors;
//        }
//    }
//
//
////
////    HashMap <Node, Node> visited = new HashMap <> ();
////    public Node cloneGraph(Node node) {
////        if (node == null) return node;
////
////        // 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回
////        if (visited.containsKey(node)) {
////            return visited.get(node);
////        }
////
////        // 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表
////        Node cloneNode = new Node(node.val, new ArrayList<>());
////        // 哈希表存储
////        visited.put(node, cloneNode);
////
////        // 遍历该节点的邻居并更新克隆节点的邻居列表
////        for (Node neighbor: node.neighbors) {
////            cloneNode.neighbors.add(cloneGraph(neighbor));
////        }
////        return cloneNode;
////    }
//
//    public int numberOfPoints(List<List<Integer>> nums) {
//        int maxN = 0, ans = 0;
//        // 使用 Lambda 表达式和 Collections.sort() 按第一个元素排序
//        nums.sort(Comparator.comparing(num -> -num.get(0)));
//        System.out.println(nums);
////        nums.sort(Comparator.comparing(o -> o.get(0)));
//        for (int i = 0; i < nums.size(); i++) {
//            int l = nums.get(i).get(0), r = nums.get(i).get(1);
//            if (l > maxN) {
//                ans += r - l + 1;
//            } else if (r > maxN) {
//                ans += r - maxN;
//            }
//            maxN = max(maxN, r);
//        }
//        return ans;
//    }
////    public String removeStars(String s) {
////        StringBuilder ans = new StringBuilder();
////        for (char c : s.toCharArray()) {
////            if (c != '*') {
////                ans.append(c);
////            } else {
////                ans.setLength(ans.length() - 1);
////            }
////        }
////        return ans.toString();
////
////    }
//
//    public void dfsMapStand(int[][] grid, int r, int c) {
//        // 处理边界情况 + 无需递归的位置做过滤处理
//        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != 1) return;
//        // 将访问过的位置做标记
//        grid[r][c] = -1;
//        // 向四个方向做递归
//        dfsMapStand(grid, r - 1, c);
//        dfsMapStand(grid, r + 1, c);
//        dfsMapStand(grid, r, c - 1);
//        dfsMapStand(grid, r, c + 1);
//    }
//
//    public String removeStars(String s) {
//        StringBuilder sb = new StringBuilder();
//        Deque<Character> stack = new ArrayDeque<>();
//        for (int i = 0; i < s.length(); i++) {
//            if (s.charAt(i) != '*') stack.push(s.charAt(i));
//            else stack.pop();
//        }
//        while (!stack.isEmpty()) {
//            sb.append(stack.pollLast());
//        }
//        return sb.toString();
//    }
//
//    public void solve(char[][] board) {
//        int r = board.length, c = board[0].length;
//        // 分别对四个边界上的元素递归遍历
//        for (int i = 0; i < r; i++) {
//            dfsSolve(board, i, 0);
//            dfsSolve(board, i, c - 1);
//        }
//        for (int i = 1; i < c - 1; i++) {
//            dfsSolve(board, 0, i);
//            dfsSolve(board, r - 1, i);
//        }
//        for (int i = 0; i < r; i++) {
//            for (int j = 0; j < c; j++) {
//                if (board[i][j] == 'V') board[i][j] = 'O';
//                else board[i][j] = 'X';
//            }
//        }
//
//    }
//
//    public void dfsSolve(char[][] board, int r, int c) {
//        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != 'O') return;
//        board[r][c] = 'V';
//        dfsSolve(board, r - 1, c);
//        dfsSolve(board, r + 1, c);
//        dfsSolve(board, r, c - 1);
//        dfsSolve(board, r, c + 1);
//    }
//
//    public int numIslands(char[][] grid) {
//        int ans = 0;
//        for (int r = 0; r < grid.length; r++) {
//            for (int c = 0; c < grid[0].length; c++) {
//                if (grid[r][c] == '1') {
//                    dfsMap(grid, r, c);
//                    ans++;
//                }
//
//            }
//        }
//        return ans;
//    }
//
//    public void dfsMap(char[][] grid, int r, int c) {
//        // 遇到边界 或 如果这个格子不是岛屿 直接返回
//        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != '1')
//            return;
//        // 将格子标记为「已遍历过」
//        grid[r][c] = '2';
//        // 访问上、下、左、右四个相邻结点
//
//        dfsMap(grid, r - 1, c);
//        dfsMap(grid, r + 1, c);
//        dfsMap(grid, r, c - 1);
//        dfsMap(grid, r, c + 1);
//    }
//
//    public boolean isArea(char[][] grid, int r, int c) {
//        return c >= 0 && c < grid[0].length && r >= 0 && r < grid.length;
//    }
//
//    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
//        int res = 0, n = chargeTimes.length;
//        long runningCostSum = 0;
//        Deque<Integer> q = new ArrayDeque<>();
//        for (int i = 0, j = 0; i < n; i++) {
//            runningCostSum += runningCosts[i];
//            while (!q.isEmpty() && chargeTimes[q.peekLast()] <= chargeTimes[i]) {
//                q.pollLast();
//            }
//            q.addLast(i);
//            while (j <= i && (i - j + 1) * runningCostSum + chargeTimes[q.peekFirst()] > budget) {
//                if (!q.isEmpty() && q.peekFirst() == j) {
//                    q.pollFirst();
//                }
//                runningCostSum -= runningCosts[j];
//                j++;
//            }
//            res = Math.max(res, i - j + 1);
//        }
//        return res;
//    }
////    List<Integer> ans = new ArrayList<>();
////
////    public boolean isValidBST(TreeNode root) {
////        dfsBST(root, ans);
////        int firstValue = ans.get(0);
////        for (int i = 1; i < ans.size(); i++) {
////            if(firstValue >= ans.get(i)) return false;
////            firstValue = ans.get(i);
////        }
////        return true;
////    }
////
////    public void dfsBST(TreeNode root, List<Integer> ans) {
////        if (root == null) return;
////        dfsBST(root.left, ans);
////        ans.add(root.val);
////        dfsBST(root.right, ans);
////    }
//
//
////    int cnt = 0;
////    Integer ans = -1;
////
////    public int kthSmallest(TreeNode root, int k) {
////        dfs(root, k);
////        return ans;
////    }
////
////    public void dfs(TreeNode root, int k) {
////        if (root == null) return;
////        dfs(root.left, k);
////        cnt++;
////        if (cnt == k) ans = root.val;
////        dfs(root.right, k);
////    }
//
//    public int maxNumOfMarkedIndices(int[] nums) {
//        int ans = 0;
//        HashMap<Integer, Integer> helper = new HashMap<>();
//        HashMap<Integer, Integer> visited = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            helper.put(nums[i], i);
//            visited.put(i, 0);
//        }
//        // 对 helpe r哈希表的key进行排序
//        List<Integer> keys = new ArrayList<>(helper.keySet());
//        Collections.sort(keys);
//        LinkedHashMap<Integer, Integer> sortedMap = new LinkedHashMap<>();
//        for (Integer key : keys) {
//            sortedMap.put(key, helper.get(key));
//        }
//        for (Map.Entry<Integer, Integer> entry1 : sortedMap.entrySet()) {
////            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
//            for (Map.Entry<Integer, Integer> entry2 : sortedMap.entrySet()) {
//                // 未被访问过
//                if (visited.get(entry1.getValue()) == 0 && visited.get(entry2.getValue()) == 0) {
//                    if (entry1.getKey() * 2 <= entry2.getKey()) {
//                        ans += 1;
//                        visited.put(entry1.getValue(), 1);
//                        visited.put(entry2.getValue(), 1);
//                    }
//                }
//
//            }
//        }
//        return ans * 2;
//    }
//
//    int minVal = Integer.MAX_VALUE;
//    TreeNode pre = null;
//
//    public int getMinimumDifference(TreeNode root) {
//        if (root == null) return 0;
//        getMinimumDifference(root.left);
//        if (pre != null && minVal > Math.abs(pre.val - root.val)) {
//            minVal = Math.abs(pre.val - root.val);
//        }
//        pre = root;
//        getMinimumDifference(root.right);
//        return minVal;
//    }
//
////    public int getMinimumDifference(TreeNode root) {
////        List<Integer> ans = new ArrayList<>();
////        getListDfs(root, ans);
////        int min = Math.abs(ans.get(0) - ans.get(1));
////        for (int i = 1; i < ans.size() - 1; i++) {
////            min = Math.min(min, Math.abs(ans.get(i) - ans.get(i + 1)));
////        }
////        return min;
////    }
////
////    public void getListDfs(TreeNode root, List<Integer> ans) {
////        if (root == null) return;
////        getListDfs(root.left, ans);
////        ans.add(root.val);
////        getListDfs(root.right, ans);
////    }
//
//
//    public int maximizeWin(int[] prizePositions, int k) {
//
//        HashMap<Integer, Integer> helper = new HashMap<>();
//        // 构造出每个位置的奖品数
//        for (int prizePosition : prizePositions) {
//            if (helper.containsKey(prizePosition)) {
//                helper.put(prizePosition, helper.get(prizePosition) + 1);
//            } else {
//                helper.put(prizePosition, 1);
//            }
//        }
//        return 0;
//    }
//
//    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
//        List<List<Integer>> ans = new ArrayList<>();
//        if (root == null) return ans;
//
//        Deque<TreeNode> treeDeque = new ArrayDeque<>();
//        Deque<TreeNode> fatherDeque = new ArrayDeque<>();
//        treeDeque.offerLast(root);
//        int depth = 1;
//        while (!treeDeque.isEmpty()) {
//            int size = treeDeque.size();
//            List<Integer> helper = new ArrayList<>();
//            for (int num = 1; num <= size; num++) {
//                TreeNode node = treeDeque.pollFirst();
//                fatherDeque.offerLast(node);
//                if (node.left != null) treeDeque.offerLast(node.left);
//                if (node.right != null) treeDeque.offerLast(node.right);
//            }
//            for (int fatherNum = 1; fatherNum <= size; fatherNum++) {
//                if (depth % 2 == 1) {
//                    helper.add(fatherDeque.pollFirst().val);
//                } else {
//                    helper.add(fatherDeque.pollLast().val);
//                }
//            }
//            depth += 1;
//            ans.add(helper);
//        }
//        return ans;
//
//    }
//
//    public List<String> binaryTreePaths(TreeNode root) {
//        List<String> ans = new ArrayList<>();
//        constructPaths(root, "", ans);
//        return ans;
//    }
//
//    public void constructPaths(TreeNode root, String path, List<String> paths) {
//        if (root != null) {
//            StringBuffer pathSB = new StringBuffer(path);
//            pathSB.append(root.val);
//            if (root.left == null && root.right == null) {
//                paths.add(pathSB.toString());
//            } else {
//                pathSB.append("->");
//                constructPaths(root.left, pathSB.toString(), paths);
//                constructPaths(root.right, pathSB.toString(), paths);
//            }
//        }
//    }
//
//
//    public List<List<Integer>> levelOrder(TreeNode root) {
//        List<List<Integer>> ans = new ArrayList<>();
//
//        if (root == null) return ans;
//        Queue<TreeNode> treeQueue = new ArrayDeque<>();
//        treeQueue.offer(root);
//        while (!treeQueue.isEmpty()) {
//            int size = treeQueue.size();
//            List<Integer> helper = new ArrayList<>();
//            for (int i = 1; i <= size; i++) {
//                TreeNode node = treeQueue.poll();
//                helper.add(node.val);
//                if (node.left != null) treeQueue.offer(node.left);
//                if (node.right != null) treeQueue.offer(node.right);
//            }
//            ans.add(helper);
//        }
//        return ans;
//    }
//
//    public List<Double> averageOfLevels(TreeNode root) {
//        List<Integer> count = new ArrayList<>();
//        List<Double> ans = new ArrayList<>();
//        dfs(root, 0, count, ans);
//        List<Double> averages = new ArrayList<>();
//        int size = ans.size();
//        for (int i = 0; i < size; i++) {
//            averages.add(ans.get(i) / count.get(i));
//        }
//        return averages;
//    }
//
//    public void dfs(TreeNode root, int level, List<Integer> count, List<Double> ans) {
//        if (root == null) return;
//        if (level < ans.size()) {
//            // 每一层的后续节点
//            count.set(level, count.get(level) + 1);
//            ans.set(level, ans.get(level) + root.val);
//        } else {
//            // 每一层的第一个节点
//            count.add(1);
//            ans.add(root.val * 1.0);
//        }
//        dfs(root.left, level + 1, count, ans);
//        dfs(root.right, level + 1, count, ans);
//    }
//
////    public List<Double> averageOfLevels(TreeNode root) {
////
////        List<Double> ans = new ArrayList<>();
//////        ans.add((double) root.val);
////        Queue<TreeNode> treeQueue = new ArrayDeque<>();
////        treeQueue.offer(root);
////        while (!treeQueue.isEmpty()) {
////            int size = treeQueue.size();
////            double sum = 0;
////            // 每一轮遍历的是同一层的全部节点
////            for (int i = 1; i <= size; i++) {
////                TreeNode node = treeQueue.poll();
////                sum += node.val;
////                if (node.left != null) treeQueue.offer(node.left);
////                if (node.right != null) treeQueue.offer(node.right);
////                if (i == size) ans.add(sum / size);
////            }
////        }
////        return ans;
////    }
//
//    public ListNode mergeNodes(ListNode head) {
//        ListNode dump = new ListNode(), helper = dump;
//        ListNode arr = head.next;
//        int nodeCnt = 0;
//        while (arr != null) {
//            nodeCnt += arr.val;
//            // 找到了一个边界（0）
//            if (arr.val == 0) {
//                arr.val = nodeCnt;
//                helper.next = arr;
//                helper = helper.next;
//                // 复原计数定义
//                nodeCnt = 0;
//            }
//            arr = arr.next;
//        }
//        return dump.next;
//    }
//
//    // 层序遍历 取每层最后一个数据
//    public List<Integer> rightSideView(TreeNode root) {
//        List<Integer> ans = new ArrayList<>();
//        if (root == null) return ans;
//        Queue<TreeNode> nodeQueue = new ArrayDeque<>();
//        nodeQueue.add(root);
//        while (!nodeQueue.isEmpty()) {
//            int size = nodeQueue.size();
//            // 找到每一层的最后一个节点
//            for (int i = 1; i <= size; i++) {
//                TreeNode node = nodeQueue.poll();
//                if (node.left != null) nodeQueue.add(node.left);
//                if (node.right != null) nodeQueue.add(node.right);
//                if (i == size) ans.add(node.val);
//            }
//        }
//        return ans;
//    }
//
//    // 二叉树右视图 DFS BFS
////    public List<Integer> rightSideView(TreeNode root) {
////        List<Integer> ans = new ArrayList<>();
////        if (root == null) return ans;
////        HashMap<Integer, Integer> rightmostValueAtDepth = new HashMap<>();
////        Queue<TreeNode> treeQueue = new ArrayDeque<>();
////        Queue<Integer> depthQueue = new ArrayDeque<>();
////        int max_depth = -1;
////        treeQueue.offer(root);
////        depthQueue.add(0);
////        while (!treeQueue.isEmpty()) {
////            TreeNode node = treeQueue.remove();
////            int depth = depthQueue.remove();
////            max_depth = Math.max(max_depth, depth);
////            rightmostValueAtDepth.put(max_depth, node.val);
////            if (node.left != null) {
////                treeQueue.add(node.left);
////                depthQueue.add(depth + 1);
////            }
////            if (node.right != null) {
////                treeQueue.add(node.right);
////                depthQueue.add(depth + 1);
////            }
////        }
////        for (int i = 0; i <= max_depth; i++) {
////            ans.add(rightmostValueAtDepth.get(i));
////        }
////        return ans;
////    }
//// 深度遍历 递归
////    List<Integer> ans;
////
////    public List<Integer> rightSideView(TreeNode root) {
////        ans = new ArrayList<>();
////        dfsRight(root, 0);
////        return ans;
////    }
////
////    private void dfsRight(TreeNode root, int depth) {
////        if (root == null) return;
////        if (depth == ans.size()) ans.add(root.val);
////        dfsRight(root.right, depth + 1);
////        dfsRight(root.left, depth + 1);
////    }
//
//
//    // 二叉树的最近公共祖先 存储父节点 技术栈 哈希Map 哈希Set
//    Map<Integer, TreeNode> parent = new HashMap<>();
//    Set<Integer> visited = new HashSet<>();
//
//    public void dfs(TreeNode root) {
//        if (root.left != null) {
//            parent.put(root.left.val, root);
//            dfs(root.left);
//        }
//        if (root.right != null) {
//            parent.put(root.right.val, root);
//            dfs(root.right);
//        }
//    }
//
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        dfs(root);
//        while (p != null) {
//            visited.add(p.val);
//            p = parent.get(p.val);
//        }
//        while (q != null) {
//            if (visited.contains(q.val)) return q;
//            q = parent.get(q.val);
//        }
//        return null;
//    }
//
//    public String clearDigits(String s) {
//        StringBuilder ans = new StringBuilder();
//        for (char c : s.toCharArray()) {
//            if (Character.isDigit(c)) ans.deleteCharAt(ans.length() - 1);
//            else ans.append(c);
//        }
//        return ans.toString();
//    }
//
////    public String clearDigits(String s) {
////        StringBuffer ans = new StringBuffer();
////        Deque<Character> deque = new ArrayDeque<>();
////        for (int i = 0; i < s.length(); i++) {
//////            int parseInt = Integer.parseInt(String.valueOf(s.charAt(i)));
////            int parseInt = s.charAt(i) - '0';
////            if (parseInt >= 0 && parseInt <= 9) deque.pop() ;
////            else deque.push(s.charAt(i));
////        }
////        while (!deque.isEmpty()){
////          ans.append(deque.pollLast());
////        }
////        return ans.toString();
////    }
//
//
//    //    int cnt = 0;
////
////    public int countNodes(TreeNode root) {
////        if (root == null) return 0;
////        return countNodes(root.left) + countNodes(root.right) + 1;
////    }
//    public int countNodes(TreeNode root) {
//        if (root == null) return 0;
//        // 获取完全二叉树树高
//        int treeHigh = highTree(root);
//        int low = 1 << treeHigh, high = (1 << (treeHigh + 1)) - 1;
//        while (low < high) {
//            int mid = (high - low + 1) / 2 + low;
//            if (exists(root, treeHigh, mid)) {
//                low = mid;
//            } else {
//                high = mid - 1;
//            }
//        }
//        return low;
//    }
//
//    public int highTree(TreeNode root) {
//        if (root == null) return 0;
//        return highTree(root.left) + 1;
//    }
//
//    public boolean exists(TreeNode root, int treeHigh, int k) {
//        int bits = 1 << (treeHigh - 1);
//        TreeNode node = root;
//        // 通过位运算实现：从最高位一步一步与目标节点判断，最终返回node != null，true即表示节点存在，否则不存在。
//        while (node != null && bits > 0) {
//            if ((bits & k) == 0) node = node.left;
//            else node = node.right;
//            bits >>= 1;
//        }
//        return node != null;
//    }
//
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> ans = new ArrayList<>();
//        Deque<TreeNode> tree = new ArrayDeque<>();
//        while (!tree.isEmpty() || root != null) {
//            while (root != null) {
//                tree.push(root);
//                root = root.left;
//            }
//            root = tree.pop();
//            ans.add(root.val);
//            root = root.right;
//        }
//        return ans;
//    }
//
//
//    // 一个按中序遍历二叉搜索树（BST）的迭代器
//    class BSTIterator {
//
//        // 化树为链的思想！ 如果按照左、根、右的顺序的话，在将左树插入到右边时会使右侧子树丢失
//        // 所以考虑倒序实现：
//        TreeNode arr = null;
//
//        public void parseTree(TreeNode node) {
//            if (node.right != null) parseTree(node.right);
//            node.right = arr;
//            arr = node;
//            if (node.left != null) parseTree(node.left);
//        }
//
//        public BSTIterator(TreeNode root) {
//            parseTree(root);
//        }
//
//        public int next() {
//            int val = arr.val;
//            arr = arr.right;
//            return val;
//        }
//
//        public boolean hasNext() {
//            return arr != null;
//        }
//    }
//
//    public int countWays(List<Integer> nums) {
//        int humanCnt = 0, ans = 0, length = nums.size();
//        nums.sort(Integer::compareTo);
//        if (nums.get(0) > humanCnt) ans++;
//        humanCnt += 1;
//        for (int i = 0; i < length - 1; i++, humanCnt++)
//            if (humanCnt > nums.get(i) && humanCnt < nums.get(i + 1)) ans++;
//        if (length > nums.get(length - 1)) ans++;
//        return ans;
//    }
//
//    public long maxStrength(int[] nums) {
//
//        long ans = 1, negative = 1;
//        int cnt = 0, cntZore = 0, maxNum = Integer.MIN_VALUE;
//        for (int num : nums) {
//            if (num > 0) ans *= num;
//            if (num < 0) {
//                cnt++;
//                negative *= -1 * num;
//                maxNum = Math.max(maxNum, num);
//            }
//            if (num == 0) cntZore++;
//        }
//        // 特殊判断
//        if (cnt == nums.length && cnt == 1) return maxNum;
//        if (cnt == 1 && cntZore + cnt == nums.length) return 0;
//        if (nums.length == 1 || cntZore == nums.length) return nums[0];
//        return cnt % 2 == 0 ? ans * negative : -1 * ans * negative / maxNum;
//    }
//
//    public int sumNumbers(TreeNode root) {
//        if (root == null) return 0;
//        Deque<TreeNode> tree = new ArrayDeque<>();
//        Deque<Integer> num = new ArrayDeque<>();
//        int sum = 0;
//        tree.offerLast(root);
//        num.offerLast(root.val);
//        while (!tree.isEmpty()) {
//            TreeNode node = tree.pollFirst();
//            int cnt = num.pollFirst();
//            if (node.left == null && node.right == null) sum += cnt;
//            else {
//                if (node.left != null) {
//                    tree.offerLast(node.left);
//                    num.offerLast(cnt * 10 + node.left.val);
//                }
//                if (node.right != null) {
//                    tree.offerLast(node.right);
//                    num.offerLast(cnt * 10 + node.right.val);
//                }
//            }
//        }
//        return sum;
//    }
//
//
////    public int sumNumbers(TreeNode root) {
////        return dfs(root,0);
////    }
////    public int dfs(TreeNode root, int prevSum) {
////        if (root == null) {
////            return 0;
////        }
////        int sum = prevSum * 10 + root.val;
////        if (root.left == null && root.right == null) {
////            return sum;
////        } else {
////            return dfs(root.left, sum) + dfs(root.right, sum);
////        }
////    }
//
//    public boolean hasPathSum(TreeNode root, int sum) {
//        if (root == null) return false;
//        if (root.left == null && root.right == null) {
//            return sum == root.val;
//        }
//        // 在众多递归次数中，只要存在一次 true，则最终结果返回 true
//        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
//    }
//
//
//    public boolean hasPathSum1(TreeNode root, int targetSum) {
//        if (root == null) return false;
//        Deque<TreeNode> tree = new ArrayDeque<>();
//        Deque<Integer> length = new ArrayDeque<>();
//        tree.offerLast(root);
//        length.offerLast(root.val);
//        while (!tree.isEmpty()) {
//            TreeNode node = tree.pollFirst();
//            int cnt = length.pollFirst();
//            if (node.left == null && node.right == null && cnt == targetSum) return true;
//            if (node.left != null) {
//                tree.offerLast(node.left);
//                length.offerLast(cnt + node.left.val);
//            }
//            if (node.right != null) {
//                tree.offerLast(node.right);
//                length.offerLast(cnt + node.right.val);
//            }
//        }
//        return false;
//    }
//
//
//    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
//        int cnt = 0;
//        for (int i = 0; i < startTime.length; i++) {
//            if (startTime[i] <= queryTime) {
//                if (endTime[i] >= queryTime) cnt++;
//            }
//        }
//        return cnt;
//    }
//
//    List<Integer> ans = new ArrayList<>();
//
//    public List<Integer> preorderTraversal(TreeNode root) {
//        preorder(root, ans);
//        return ans;
//    }
//
//    // 层序
//    public void preorder(TreeNode root, List<Integer> res) {
//        Deque<TreeNode> tree = new ArrayDeque<>();
//        TreeNode node = root;
//        while (!tree.isEmpty() || node != null) {
//            while (node != null) {
//                res.add(node.val);
//                tree.push(node);
//                node = node.left;
//            }
//            node = tree.pop();
//            node = node.right;
//        }
//
////        while (!tree.isEmpty()) {
////            TreeNode node = tree.pollFirst();
////            res.add(node.val);
////            if (node.left != null) tree.offerLast(node.left);
////            if (node.right != null) tree.offerLast(node.right);
////        }
//    }
//
//
////    List<Integer> ans = new ArrayList<>();
////
////    public List<Integer> preorderTraversal(TreeNode root) {
////        preorder(root, ans);
////        return ans;
////    }
////    public void preorder(TreeNode root, List<Integer> res) {
////        if (root == null) {
////            return;
////        }
////        res.add(root.val);
////        preorder(root.left, res);
////        preorder(root.right, res);
////    }
//
////    TreeNode pre = null;
////
////    public void flatten(TreeNode root) {
////        if (root == null) return;
////        flatten(root.left);
////        flatten(root.right);
////        root.right = pre;
////        root.left = null;
////        pre = root;
////    }
//
//    public boolean canMakeSquare(char[][] grid) {
//        for (int i = 0; i <= 1; i++) {
//            for (int j = 0; j <= 1; j++) {
//                if (check(grid, i, j)) {
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//
//    public boolean check(char[][] grid, int x, int y) {
//        int count = 0;
//        for (int i = 0; i <= 1; i++) {
//            for (int j = 0; j <= 1; j++) {
//                if (grid[x + i][y + j] == 'B') {
//                    count++;
//                }
//            }
//        }
//        return count != 2;
//    }
//
//    public long sumDigitDifferences(int[] nums) {
//
//        int m = nums.length, n = 1;
//        int sum = 0, help = nums[0];
//        while (help / 10 != 0) {
//            n++;
//            help /= 10;
//        }
//        int[][] tmp = new int[m][n];
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                tmp[i][j] = nums[i] % 10;
//                nums[i] = nums[i] / 10;
//            }
//        }
//        for (int j = 0; j < n; j++) {
//            for (int i = 0; i < m - 1; i++) {
//                if (tmp[j][i] != tmp[i + 1][j]) sum++;
//            }
//        }
//        return sum;
//    }
//
//    public boolean satisfiesConditions(int[][] grid) {
//        int m = grid.length, n = grid[0].length;
//        int flag = 0;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//
//                if (i < m - 1 && grid[i][j] != grid[i + 1][j]) return false;
//                if (j < n - 1 && grid[i][j] != grid[i][j + 1]) return false;
//
//                // 数组的最后一行且不是最后一列，仅需判断右侧
//                if (i == m - 1 && j != n - 1) {
////                    if (grid[i][j] == grid[i][j + 1]) return false;
//                }
//                // 数组的最后一列且不是最后一行，仅需判断下侧
//                else if (j == n - 1 && i != m - 1) {
////                    if (grid[i][j] != grid[i + 1][j]) return false;
//                }
//                // 数组的最后一列且是最后一行的一个元素，仅需判断右侧
//                else if (j == n - 1 && i == m - 1) {
//                    continue;
//                } else {
//                    if (grid[i][j] == grid[i][j + 1]) return false;
//                    if (grid[i][j] != grid[i + 1][j]) return false;
//                }
//            }
//        }
//        return true;
//    }
//
////    class Node {
////        public int val;
////        public Node left;
////        public Node right;
////        public Node next;
////
////        public Node() {
////        }
////
////        public Node(int _val) {
////            val = _val;
////        }
////
////        public Node(int _val, Node _left, Node _right, Node _next) {
////            val = _val;
////            left = _left;
////            right = _right;
////            next = _next;
////        }
////    }
//
//    // 层序遍历
////    public Node connect(Node root) {
////        if (root == null) return null;
////        Deque<Node> tree = new ArrayDeque<>();
////        tree.offerLast(root);
////        while (!tree.isEmpty()) {
////            int size = tree.size();
////            Node last = null;
////            for (int i = 0; i < size; i++) {
////                Node current = tree.pollFirst();
////                // 将当前节点的左右子节点加入队列
////                if (current.left != null) tree.offerLast(current.left);
////                if (current.right != null) tree.offerLast(current.right);
////                if (i != 0) last.next = current;
////                last = current;
////            }
////        }
////
////        return root;
////    }
//
//    int post_idx;
//    int[] postorder;
//    int[] inorder;
//    Map<Integer, Integer> idx_map = new HashMap<>();
//    int[] preorder;
//
//    public TreeNode helper(int in_left, int in_right) {
//        // 如果这里没有节点构造二叉树了，就结束
//        if (in_left > in_right) {
//            return null;
//        }
//
//        // 选择 post_idx 位置的元素作为当前子树根节点
//        int root_val = preorder[post_idx];
//        TreeNode root = new TreeNode(root_val);
//
//        // 根据 root 所在位置分成左右两棵子树
//        int index = idx_map.get(root_val);
//
//        // 下标减一
//        post_idx++;
//        // 构造左子树
//        root.left = helper(in_left, index - 1);
//        // 构造右子树
//        root.right = helper(index + 1, in_right);
//        return root;
//    }
//
//
//    public Map<Integer, Integer> indexMap;
//
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//
//        int n = preorder.length;
//        // 构造哈希映射，帮助我们快速定位根节点
//        indexMap = new HashMap<>();
//        for (int i = 0; i < n; i++) {
//            indexMap.put(inorder[i], i);
//        }
//        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
//
//    }
//
//    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right,
//                                int inorder_left, int inorder_right) {
//        if (preorder_left > preorder_right) {
//            return null;
//        }
//
//        // 前序遍历中的第一个节点就是根节点
//        // 在中序遍历中定位根节点
//        int inorder_root = indexMap.get(preorder[preorder_left]);
//
//        // 先把根节点建立出来
//        TreeNode root = new TreeNode(preorder[preorder_left]);
//        // 得到左子树中的节点数目
//        int size_left_subtree = inorder_root - inorder_left;
//        // 递归地构造左子树，并连接到根节点
//        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
//        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
//        // 递归地构造右子树，并连接到根节点
//        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
//        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
//        return root;
//    }
//
//    public TreeNode myBuildTree2(int[] inorder, int[] postorder, int inorder_left, int inorder_right,
//                                 int postorder_left, int postorder_right) {
//        if (inorder_left > inorder_right) return null;
//
//        // 后序遍历中的最后一个节点就是根节点
//        int postorder_root = postorder_right;
//        // 在中序遍历中定位根节点
//        int inorder_root = indexMap.get(postorder[postorder_root]);
//        // 得到左子树中的节点数目
//        int size_left_subtree = inorder_root - inorder_left;
//        // 先把根节点建立出来
//        TreeNode root = new TreeNode(postorder[postorder_root]);
//        // 递归地构造左子树，并连接到根节点
//        root.left = myBuildTree2(inorder, postorder, inorder_left, inorder_root - 1, postorder_left, postorder_left + size_left_subtree - 1);
//        // 递归地构造右子树，并连接到根节点
//        root.right = myBuildTree2(inorder, postorder, inorder_root + 1, inorder_right, postorder_left + size_left_subtree, postorder_right - 1);
//        return root;
//    }
//
//
//    // 层序遍历判断二叉树是否对称
//    public boolean isSymmetric(TreeNode root) {
//        Queue<TreeNode> tree = new LinkedList<>();
//        tree.offer(root);
//        tree.offer(root);
//        while (!tree.isEmpty()) {
//            TreeNode node1 = tree.poll();
//            TreeNode node2 = tree.poll();
//            if (node1 == null && node2 == null) {
//                continue;
//            }
//            if ((node1 == null || node2 == null) || (node1.val != node2.val)) {
//                return false;
//            }
//
//            tree.offer(node1.left);
//            tree.offer(node2.right);
//
//            tree.offer(node1.right);
//            tree.offer(node2.left);
//        }
//        return true;
//    }
//
//    // 递归法判断二叉树是否对称
//    public boolean isSymmetricDg(TreeNode root) {
//        return check(root, root);
//    }
//
//    public boolean check(TreeNode p, TreeNode q) {
//        if (p == null && q == null) {
//            return true;
//        }
//        if (p == null || q == null) {
//            return false;
//        }
//        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
//    }
//
//
//    // 反转二叉树操作——递归实现方式
//    public TreeNode invertTreeDg(TreeNode root) {
//        if (root == null) return null;
//
//        if (root.left != null || root.right != null) {
//            TreeNode tmp = root.left;
//            root.left = root.right;
//            root.right = tmp;
//            invertTreeDg(root.left);
//            invertTreeDg(root.right);
//        }
//        return root;
//    }
//
//    // 反转二叉树操作——层序遍历操作
//    public TreeNode invertTree(TreeNode root) {
//        Deque<TreeNode> tree = new ArrayDeque<>();
//        if (root != null) tree.offerLast(root);
//        while (!tree.isEmpty()) {
//            TreeNode node = tree.pollFirst();
//            TreeNode tmp = node.left;
//            node.left = node.right;
//            node.right = tmp;
//            if (node.left != null) {
//                tree.offerLast(node.left);
//            }
//            if (node.right != null) {
//                tree.offerLast(node.right);
//            }
//        }
//        return root;
//    }
//
//
//    // 二叉树的最大深度
//    public int maxDepth(TreeNode root) {
//        if (root == null) return 0;
//        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
//    }
//
//    // DFS判断两个二叉树是否相同
//    public boolean isSameTreeDfs(TreeNode p, TreeNode q) {
//        if (p == null && q == null) return true;
//        else if (p == null || q == null) {
//            return false;
//        } else if (p.val != q.val) {
//            return false;
//        } else {
//            return isSameTreeDfs(p.left, q.left) && isSameTreeDfs(p.right, q.right);
//        }
//    }
//
//    // BFS判断两个二叉树是否相同
//    public boolean isSameTreeBfs(TreeNode p, TreeNode q) {
//        if (p == null && q == null) return true;
//        else if (p == null || q == null) {
//            return false;
//        }
//        Deque<TreeNode> tree1 = new ArrayDeque<>();
//        Deque<TreeNode> tree2 = new ArrayDeque<>();
//        // 初始化队列根节点
//        tree1.push(p);
//        tree2.push(q);
//        while (!tree1.isEmpty() && !tree2.isEmpty()) {
//            // 栈 : push pop peek
//            // 队列 : offer poll
//            // 全能 : 双端队列 —— 对队列的操作：插入操作的是尾部 删除操作的是头部
//            TreeNode node1 = tree1.poll();
//            TreeNode node2 = tree2.poll();
//            if (node1.val != node2.val) return false;
//            TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
//            // 异或符 当且仅当左右表达式的值不同时返回true；两次均为true或者均为false时返回false
//            if (left1 == null ^ left2 == null) return false;
//            if (right1 == null ^ right2 == null) return false;
//            if (left1 != null) tree1.push(left1);
//            if (right1 != null) tree1.push(right1);
//            if (left2 != null) tree2.push(left2);
//            if (right2 != null) tree2.push(right2);
//        }
//        return tree1.isEmpty() && tree2.isEmpty();
//    }
//
//    public ListNode partition(ListNode head, int x) {
//        ListNode dump = new ListNode(-1, head);
//        ListNode flag = dump.next;
//        Deque<ListNode> small = new ArrayDeque<>();
//        Deque<ListNode> big = new ArrayDeque<>();
//        if (head == null || head.next == null) return head;
//        while (flag != null) {
//            // 小于 x 的节点依次入栈
//            if (flag.val < x) small.push(flag);
//                // 大于 x 的节点依次入栈
//            else big.push(flag);
//            flag = flag.next;
//        }
//        if (!big.isEmpty()) flag = big.removeLast();
//        dump.next = flag;
//        // 大于 x 的数使用尾插法
//        while (!big.isEmpty()) {
//            flag.next = big.removeLast();
//            flag = flag.next;
//        }
//        if (flag != null) flag.next = null;
//        // 小于 x 的数使用头插法
//        while (!small.isEmpty()) {
//            ListNode tmp = small.pop();
//            tmp.next = dump.next;
//            dump.next = tmp;
//        }
//        return dump.next;
//    }
//
//
//    public int evalRPN(String[] tokens) {
//        // 时间 2024-05-18 22：50
//        Deque<Integer> stack = new ArrayDeque<>();
//        int left, right, mid;
//        for (String string : tokens) {
//            if (!"+".equals(string) && !"-".equals(string) && !"*".equals(string) && !"/".equals(string)) {
//                stack.push(Integer.valueOf(string));
//            } else if ("+".equals(string)) {
//                stack.push(stack.pop() + stack.pop());
//            } else if ("-".equals(string)) {
//                stack.push(-stack.pop() + stack.pop());
//            } else if ("*".equals(string)) {
//                stack.push(stack.pop() * stack.pop());
//            } else {
//                right = stack.pop();
//                left = stack.pop();
//                mid = left / right;
//                stack.push(mid);
//            }
//        }
//        return stack.peek();
//    }
//
////    class Node {
////        int val;
////        Node next;
////        Node random;
////
////        public Node(int val) {
////            this.val = val;
////            this.next = null;
////            this.random = null;
////        }
////    }
////
////    public Node copyRandomList(Node head) {
////        if (head == null) return null;
////        // 复制一份拷贝节点插入原节点后
////        for (Node node = head; node != null; node = node.next.next) {
////            Node newNode = new Node(node.val);
////            newNode.next = node.next;
////            node.next = newNode;
////        }
////        // 处理random节点信息
////        for (Node node = head; node != null; node = node.next.next) {
////            Node newNode = node.next;
////            if (node.random == null) newNode.random = null;
////            else
////                newNode.random = node.random.next;
////        }
////        // 剥离出复制的节点
////        Node newHead = head.next;
////        for (Node node = head; node != null; node = node.next) {
////            Node newNode = node.next;
////            // 因为最后一个node的后边一定有一个newNode所以不会为null
////            node.next = node.next.next;
////            newNode.next = (newNode.next == null) ? null : newNode.next.next;
////        }
////
////        return newHead;
////    }
//
//    public String simplifyPath(String path) {
//        Deque<String> stack = new ArrayDeque<>();
//        String[] tmp = path.split("/");
//        for (String s : tmp) {
//            if ("..".equals(s) && !stack.isEmpty()) {
//                stack.pollLast();
//            } else if (!s.isEmpty() && !".".equals(s) && !"..".equals(s)) {
//                stack.offerLast(s);
//            }
//        }
//        StringBuilder sb = new StringBuilder();
//        // sb.append('/');
//        if (stack.isEmpty()) return "/";
//        while (!stack.isEmpty()) {
//            sb.append('/');
//            sb.append(stack.pollFirst());
//        }
//        return sb.toString();
//    }
//
//    public boolean isValid(String s) {
//        Stack<Character> stack = new Stack<>();
//        char[] ch = s.toCharArray();
//        if (ch.length <= 1) return false;
//        for (char c : ch) {
//            if (c == '(') stack.push(c);
//            else if (c == '{') stack.push(c);
//            else if (c == '[') stack.push(c);
//            else if (c == ')') {
//                if (stack.isEmpty()) return false;
//                else if (stack.pop() != '(') return false;
//            } else if (c == ']') {
//                if (stack.isEmpty()) return false;
//                else if (stack.pop() != '[') return false;
//            } else if (c == '}') {
//                if (stack.isEmpty()) return false;
//                else if (stack.pop() != '{') return false;
//            }
//        }
//        return stack.isEmpty();
//    }
//
//
////        int[] ratings = {0, 1, 2, 4, 5, 7};
////        int[] play = {2, 3, 10, 5, 7, 8, 9};
////        int[][] matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
////        String s = "ab";
////        String t = "ba";
////        setZeroes(matrix);
////        for (int[] ints : matrix) {
////            for (int i : ints) {
////                System.out.print(i + " ");
////            }
////            System.out.println("\t");
////        }
//
//    public int findMinArrowShots(int[][] points) {
//
//        Arrays.sort(points, Comparator.comparingInt(a -> a[0]));
//        int ans = 1, arrow = points[0][1];
//        for (int[] point : points) {
//            if (point[0] > arrow) {
//                arrow = point[1];
//                ans++;
//            }
//        }
//        return ans;
////        for (int[] point : points) {
////            if(index==-1||point[0]>help[index][1]){
////                help[++index] = point;
////            }else{
////                // 存放交集区间
////                help[index][0] = Math.max(help[index][0],point[0]);
////                help[index][1] = Math.min(help[index][1],point[1]);
////            }
////        }
//    }
//
//    public int[][] merge(int[][] intervals) {
//        // 14点58分 2024年1月7日
//        int rows = intervals.length;
//        int[][] ans = new int[rows][2];
//        // 先以区间起始位置排序 保证后一个区间的起始位置一定大于等于前一个区间的起始位置
//        /*
//        降序排序的时候使用这个：
//        Arrays.sort(intervals, Comparator.comparingInt(v -> v[0]).reversed());
//          */
//        Arrays.sort(intervals, Comparator.comparingInt(v -> v[0]));
//        int flag = -1;
//        for (int[] interval : intervals) {
//            if (flag == -1 || interval[0] > ans[flag][1]) {
//                ans[++flag] = interval;
//            } else {
//                ans[flag][1] = Math.max(interval[1], ans[flag][1]);
//            }
//        }
//        return Arrays.copyOf(ans, flag + 1);
//    }
//
//    public void gameOfLife(int[][] board) {
//
//        // 增加细胞状态，防止原地更新后的值对后续操作产生影响
//        int[] neighbors = {0, 1, -1};
//        int rows = board.length;
//        int cols = board[0].length;
//
//        for (int row = 0; row < rows; row++) {
//            for (int col = 0; col < cols; col++) {
//                int liveNeibors = 0;
//                for (int i = 0; i < 3; i++) {
//                    for (int j = 0; j < 3; j++) {
//                        if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
//                            int r = row + neighbors[i];
//                            int c = col + neighbors[j];
//
//                            if ((r < rows && r >= 0) && (c < cols && c >= 0) && Math.abs(board[r][c]) == 1) {
//                                liveNeibors++;
//                            }
//                        }
//                    }
//                }
//                if ((board[row][col] == 1) && (liveNeibors < 2 || liveNeibors > 3)) {
//                    // 代表细胞状态由 活 到 死
//                    board[row][col] = -1;
//                }
//                if (board[row][col] == 0 && liveNeibors == 3) {
//                    // 代表细胞状态由 死 到 活
//                    board[row][col] = 2;
//                }
//            }
//        }
//        // 遍历 board 得到一次更新后的状态
//        for (int row = 0; row < rows; row++) {
//            for (int col = 0; col < cols; col++) {
//                if (board[row][col] > 0) {
//                    board[row][col] = 1;
//                } else {
//                    board[row][col] = 0;
//                }
//            }
//        }
//    }
//
//    // 使用递归实现辗转相除法求最大公约数
//    public int findGCD(int a, int b) {
//        if (b == 0) {
//            return a;
//        } else {
//            return findGCD(b, a % b);
//        }
//    }
//
//
//    public ListNode reverseBetween(ListNode head, int left, int right) {
//        // 10点57分 2024年5月27日
//        // 设置 dummyNode 是这一类问题的一般做法
//        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
//        ListNode dummyNode = new ListNode(-1);
//        dummyNode.next = head;
//        ListNode pre = dummyNode;
//        // 找到左链表的最右侧
//        for (int i = 0; i < left - 1; i++) {
//            pre = pre.next;
//        }
//        ListNode cur = pre.next;
//        ListNode next;
//        for (int i = 0; i < right - left; i++) {
//            next = cur.next;
//            cur.next = next.next;
//            next.next = pre.next;
//            pre.next = next;
//        }
//        return dummyNode.next;
//
//    }
//
//    public ListNode insertGreatestCommonDivisors(ListNode head) {
//        ListNode p = head.next;
//        ListNode q = head;
//        if (p == null) return head;
//        while (p != null) {
//            ListNode gcd = new ListNode(findGCD(p.val, q.val));
//            q.next = gcd;
//            gcd.next = p;
//            q = p;
//            p = p.next;
//        }
//        return head;
//    }
//
//    public int numRescueBoats(int[] people, int limit) {
//        // 22点51分 2024年6月10日
//        int[] sortedArray = Arrays.stream(people).sorted().toArray();
//        int cnt = 0, left = 0, right = sortedArray.length - 1;
//        while (left <= right) {
//            // 第一+ 最后装的下 继续
//            if (sortedArray[left] + sortedArray[right] <= limit) left++;
//            // 第一+ 最后装不下 那么最后一个跟谁一起都不行 只能自己
//            right--;
//            cnt++;
//        }
//        return cnt;
//    }
//
//    public void setZeroes(int[][] matrix) {
//
//        int columns = matrix.length, rows = matrix[0].length;
//        boolean flagC = false, flagR = false;
//        for (int i = 0; i < rows; i++) {
//            if (matrix[0][i] == 0) {
//                flagC = true;
//                break;
//            }
//        }
//        for (int[] ints : matrix) {
//            if (ints[0] == 0) {
//                flagR = true;
//                break;
//            }
//        }
//        for (int i = 0; i < columns; i++) {
//            for (int j = 0; j < rows; j++) {
//                if (matrix[i][j] == 0) {
//                    matrix[0][j] = 0;
//                    matrix[i][0] = 0;
//                    break;
//                }
//            }
//        }
//        for (int i = 1; i < columns; i++) {
//            for (int j = 1; j < rows; j++) {
//                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
//                    matrix[i][j] = 0;
//                }
//            }
//        }
//        if (flagC) {
//            for (int i = 0; i < rows; i++) {
//                matrix[0][i] = 0;
//            }
//        }
//        if (flagR) {
//            for (int i = 0; i < columns; i++) {
//                matrix[i][0] = 0;
//            }
//        }
////        // 2024年1月6日 13点14分
////        // 空间复杂度为O(m+n)
////        int columns = matrix.length, rows = matrix[0].length;
////        int[] helpC = new int[columns];
////        int[] helpR = new int[rows];
////        int k = 0;
////        // 构建辅助数组
////        for (int i = 0; i < columns; i++) {
////            for (int j = 0; j < rows; j++) {
////                if (matrix[i][j] == 0) {
////                    helpR[j] = 1;
////                    helpC[i] = 1;
////                }
////            }
////        }
////        for (int i = 0; i < columns; i++) {
////            for (int j = 0; j < rows; j++) {
////                if (helpC[i] == 1 || helpR[j] == 1) {
////                    matrix[i][j] = 0;
////                }
////            }
////        }
////        // 对行进行操作 若有某一行存在0 则置此行所有值为0
////        for (int i = 0; i < columns; i++) {
////            if (helpC[i] == 1) {
////                for (int j = 0; j < rows; j++) {
////                    matrix[i][j] = 0;
////                }
////            }
////        }
////        // 对列进行操作 若有某一列存在0 则置此行所有值为0
////        for (int i = 0; i < rows; i++) {
////            if (helpR[i] == 1) {
////                for (int j = 0; j < columns; j++) {
////                    matrix[j][i] = 0;
////                }
////            }
////        }
//    }
//
//    public List<String> summaryRanges(int[] nums) {
//        //
//        int n = nums.length;
//        List<String> ans = new ArrayList<>();
//
//        int i = 0;
//        while (i < n) {
//            int low = i;
//            i++;
//            while (i < n && nums[i] == nums[i - 1] + 1) {
//                i++;
//            }
//            int high = i - 1;
//            StringBuilder tmp = new StringBuilder(Integer.toString(nums[low]));
//            if (low < high) {
//                tmp.append("->");
//                tmp.append(nums[high]);
//            }
//            ans.add(tmp.toString());
//        }
//        return ans;
//    }
//
//    public List<List<String>> groupAnagrams(String[] strs) {
//        Map<String, List<String>> map = new HashMap<>();
//        for (String str : strs) {
//            char[] array = str.toCharArray();
//            Arrays.sort(array);
//            String key = new String(array);
//            List<String> list = map.getOrDefault(key, new ArrayList<>());
//            list.add(str);
//            map.put(key, list);
//        }
//        return new ArrayList<>(map.values());
//
//    }
//
//    public boolean containsNearbyDuplicate(int[] nums, int k) {
//        // 2024年1月2日 10点22分
//        HashMap<Integer, Integer> map = new HashMap<>();
//        int len = nums.length;
//        int dis = Integer.MAX_VALUE;
//        for (int i = 0; i < len; i++) {
//            if (!map.containsKey(nums[i])) {
//                map.put(nums[i], i);
//            } else {
//                dis = Math.min(Math.abs(map.get(nums[i]) - i), dis);
//                map.put(nums[i], i);
//            }
//        }
//        return dis <= k;
//    }
//
//    public boolean isAnagram(String s, String t) {
//        HashMap<Character, Integer> mapS = new HashMap<>();
//        int lenS = s.length(), lenT = t.length();
//        int cnt;
//        if (lenS != lenT) return false;
//        for (int i = 0; i < lenS; i++) {
//            if (!mapS.containsKey(s.charAt(i))) {
//                mapS.put(s.charAt(i), 1);
//            } else {
//                cnt = mapS.get(s.charAt(i));
//                cnt++;
//                mapS.put(s.charAt(i), cnt);
//            }
//        }
//        for (int i = 0; i < lenS; i++) {
//            if (!mapS.containsKey(t.charAt(i))) {
//                return false;
//            }
//            mapS.put(t.charAt(i), mapS.get(t.charAt(i)) - 1);
//            if (mapS.get(t.charAt(i)) == 0) mapS.remove(t.charAt(i));
//        }
//
//        return mapS.isEmpty();
//    }
//
//    public boolean isHappy(int n) {
//        int ans = 0, tmp = n;
//        HashMap<Integer, Integer> map = new HashMap<>();
//        while (n != 0) {
//            int x = n % 10;
//            ans += x * x;
//            n /= 10;
//            if (n == 0) {
//                if (ans == 1) return true;
//                if (!map.containsKey(tmp)) {
//                    map.put(tmp, ans);
//                } else {
//                    return false;
//                }
//                n = ans;
//                ans = 0;
//                tmp = n;
//            }
//        }
//        return false;
//    }
//
//    public boolean wordPattern(String pattern, String s) {
//        HashMap<Character, String> mapF = new HashMap<>();
//        HashMap<String, Character> mapB = new HashMap<>();
//        String[] split = s.split(" ");
//        if (split.length != pattern.length()) return false;
//        for (int i = 0; i < pattern.length(); i++) {
//            if (!mapF.containsKey(pattern.charAt(i))) {
//                mapF.put(pattern.charAt(i), split[i]);
//                if (!mapB.containsKey(split[i])) {
//                    mapB.put(split[i], pattern.charAt(i));
//                } else {
//                    return false;
//                }
//
//            } else {
//                if (!mapF.get(pattern.charAt(i)).equals(split[i])) {
//                    return false;
//                }
//            }
//        }
//        return true;
//    }
//
//    String[] ss = new String[]{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
//    int[] nums = new int[]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
//
//    public String dayOfTheWeek(int day, int month, int year) {
//        int ans = 4;
//        for (int i = 1971; i < year; i++) {
//            boolean isLeap = (i % 4 == 0 && i % 100 != 0) || i % 400 == 0;
//            ans += isLeap ? 366 : 365;
//        }
//        for (int i = 1; i < month; i++) {
//            ans += nums[i - 1];
//            if (i == 2 && ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)) ans++;
//        }
//        ans += day;
//        return ss[ans % 7];
//    }
//
//    public int maxPoints(int[][] points) {
//        int len = points.length;
//        int a = 0;
//        for (int i = 0; i < len; i++) {
//            a = points[0][i];
//        }
//        return a;
//    }
//
//    public boolean isIsomorphic(String s, String t) {
//
//        int len = s.length();
//        HashMap<Character, Character> mapS = new HashMap<>();
//        HashMap<Character, Character> mapT = new HashMap<>();
//
//        for (int i = 0; i < len; i++) {
//            if (!mapS.containsKey(s.charAt(i))) {
//                mapS.put(s.charAt(i), t.charAt(i));
//                if (mapT.containsKey(t.charAt(i))) {
//                    return false;
//                }
//                mapT.put(t.charAt(i), s.charAt(i));
//            } else {
//                if (mapS.get(s.charAt(i)) != t.charAt(i)) {
//                    return false;
//                }
//            }
//        }
//        return true;
//
//    }
//
//    public int lengthOfLongestSubstring(String s) {
//        HashMap<Character, Integer> map = new HashMap<>();
//        int ans = 0, sum = 0;
//        for (int i = 0; i < s.length(); i++) {
//            if (!map.containsKey(s.charAt(i))) {
//                map.put(s.charAt(i), 1);
//                sum++;
//                ans = Math.max(ans, sum);
//            } else {
//                sum--;
//
//                map.remove(s.charAt(i));
//            }
//        }
//        return ans;
//    }
//
//    public int buyChoco(int[] prices, int money) {
//        Arrays.sort(prices);
//        int midTool = money - prices[0] - prices[1];
////        for (int price : prices) {
////            if (price <= money && cnt < 2) {
////                money -= price;
////                cnt++;
////            } else {
////                if (cnt == 2) return money;
////                else return oriMoney;
////            }
////        }
//        return midTool < 0 ? money : midTool;
//    }
//
//    public int minSubArrayLen(int target, int[] nums) {
//        int len = nums.length;
//        int left = 0, right = -1;
//        int sum = 0, minL = Integer.MAX_VALUE;
//        while (left <= len - 1) {
//            if (sum >= target) {
//                minL = Math.min(minL, right - left + 1);
//                sum -= nums[left];
//                left++;
//            } else {
//                right++;
//                if (right >= len) break;
//                sum += nums[right];
//            }
//        }
//        return minL == Integer.MAX_VALUE ? 0 : minL;
////        int n = nums.length;
////        if (n == 0) {
////            return 0;
////        }
////        int ans = Integer.MAX_VALUE;
////        int[] sums = new int[n + 1];
////        // 为了方便计算，令 size = n + 1
////        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
////        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
////        // 以此类推
////        for (int i = 1; i <= n; i++) {
////            sums[i] = sums[i - 1] + nums[i - 1];
////        }
////        for (int i = 1; i <= n; i++) {
////            int target = s + sums[i - 1];
////            int bound = Arrays.binarySearch(sums, target);
////            // key not find--return:-(low + 1)
////            if (bound < 0) {
////                // 这一步处理其实是获取low的位置
////                bound = -bound - 1;
////            }
////            if (bound <= n) {
////                ans = Math.min(ans, bound - (i - 1));
////            }
////        }
////        return ans == Integer.MAX_VALUE ? 0 : ans;
//    }
//
////    public static int minSubArrayLen(int target, int[] nums) {
////        int len = nums.length;
////        // 0代表从未大于等于过target 1表示求和大于等于过target
////        int flag = 0;
////        int minL = len,j = 0;
////        int sum = nums[0];
////        if(sum >= target) return 1;
////        for(int i=j+1;i<len;i++){
////            for(j=i;j<len;j++){
////                sum += nums[j];
////                if(sum>=target) {
////                    minL = Math.min(minL,j-i+1);
////                    sum = 0;
////                    flag = 1;
////                    break;
////                }
////            }
////        }
////        return (flag == 1) ? minL:0;
////    }
//
//    public boolean canConstruct(String ransomNote, String magazine) {
//        HashMap<Character, Integer> ansMap = new HashMap<>();
//        int len1 = ransomNote.length() - 1;
//        int len2 = magazine.length() - 1;
//        int cnt = 0;
//        while (len2 >= 0) {
//            if (ansMap.containsKey(magazine.charAt(len2))) {
//                cnt = ansMap.get(magazine.charAt(len2)) + 1;
//                ansMap.put(magazine.charAt(len2), cnt);
//            } else {
//                ansMap.put(magazine.charAt(len2), 1);
//            }
//            len2--;
//        }
//        while (len1 >= 0) {
//            if (ansMap.containsKey(ransomNote.charAt(len1)) && ansMap.get(ransomNote.charAt(len1)) >= 1) {
//                cnt = ansMap.get(ransomNote.charAt(len1)) - 1;
//                ansMap.put(ransomNote.charAt(len1), cnt);
//            } else {
//                return false;
//            }
//            len1--;
//        }
//        return true;
//    }
//
//    public List<List<Integer>> threeSum(int[] nums) {
//        HashMap<Character, Integer> ansMap = new HashMap<>();
//        List<List<Integer>> ans = new ArrayList<>();
//        int len = nums.length;
////        Arrays.sort();
//        int[] newNums = Arrays.stream(nums).sorted().toArray();
//        int cnt = 0;
//        for (int i = 0; i < len; i++) {
//            for (int j = i + 1; j < len; j++) {
//                for (int k = j + 1; k < len; k++) {
//                    if (cnt == 0 && newNums[i] + newNums[j] + newNums[k] == 0) {
//                        ans.add(new ArrayList<>());
//                        ans.get(cnt).add(newNums[i]);
//                        ans.get(cnt).add(newNums[j]);
//                        ans.get(cnt).add(newNums[k]);
//                        cnt++;
//                    } else if (cnt != 0 && newNums[k] != ans.get(cnt - 1).get(2)) {
//                        if (newNums[i] + newNums[j] + newNums[k] == 0) {
//                            ans.add(new ArrayList<>());
//                            ans.get(cnt).add(newNums[i]);
//                            ans.get(cnt).add(newNums[j]);
//                            ans.get(cnt).add(newNums[k]);
//                            cnt++;
//                        }
//                    }
//                }
//            }
//        }
//        return ans;
//    }
//
//    public List<List<Integer>> joinList(int cnt, int i, int j, int k) {
//        List<List<Integer>> ans = new ArrayList<>();
//        ans.add(new ArrayList<>());
//        ans.get(cnt).add(i);
//        ans.get(cnt).add(j);
//        ans.get(cnt).add(k);
//        return ans;
//    }
//
//    public int maxArea(int[] height) {
//        // 2023年12月27日 13点41分
//        // 双指针
//        int left = 0, right = height.length - 1;
//        int maxV = 0;
//        while (left < right) {
//            maxV = Math.max(maxV, (right - left) * Math.min(height[left], height[right]));
//            if (height[left] > height[right]) {
//                right--;
//            } else {
//                left++;
//            }
//        }
//        return maxV;
//    }
//
//    public int isWinner(int[] player1, int[] player2) {
//        int cnt1 = 0, cnt2 = 0;
//        int len = player1.length;
//        int sumP1 = 0, sumP2 = 0;
////        boolean flag1 = false, flag2 = false;
//        for (int i = 0; i < len; i++) {
//            if (cnt1 > 0) {
//                cnt1--;
//                sumP1 += 2 * player1[i];
//            } else {
//                sumP1 += player1[i];
//            }
//            if (cnt2 > 0) {
//                cnt2--;
//                sumP2 += 2 * player2[i];
//            } else {
//                sumP2 += player2[i];
//            }
//            if (player1[i] == 10) {
//                cnt1 = 2;
//            }
//            if (player2[i] == 10) {
//                cnt2 = 2;
//            }
//        }
//        if (sumP1 == sumP2) {
//            return 0;
//        } else if (sumP1 > sumP2) {
//            return 1;
//        } else {
//            return 2;
//        }
//    }
//
//    public boolean isSubsequence(String s, String t) {
//        int tp = 0;
//        for (int i = 0; i < s.length(); ) {
//            if (s.charAt(i) == t.charAt(tp)) {
//                i++;
//                if (i == s.length()) return true;
//            }
//            tp++;
//            if (tp == t.length()) return false;
//        }
//
//        return false;
//    }
//
//    public int[] twoSum1(int[] numbers, int target) {
//
//
//        // 2023年12月26日 22点52分
//        // 使用二分查找--因为时有序数组
//        for (int i = 0; i < numbers.length; i++) {
//            int low = i + 1, high = numbers.length - 1;
//            while (low <= high) {
//                int mid = (high - low) / 2 + low;
//                if (numbers[mid] == target - numbers[i]) {
//                    return new int[]{i + 1, mid + 1};
//                } else if (numbers[mid] > target - numbers[i]) {
//                    high = mid - 1;
//                } else {
//                    low = mid + 1;
//                }
//            }
//        }
//        return new int[]{-1, -1};
//
//
//    }
//
//    public int[] twoSum(int[] nums, int target) {
//        HashMap<Integer, Integer> map = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            if (map.containsKey(target - nums[i])) {
//                return new int[]{map.get(target - nums[i]), i};
//            }
//            map.put(nums[i], i);
//        }
//        return null;
//        // for(int i=0;i<nums.length;i++){
//        //     for(int j=i+1;j<nums.length;j++){
//        //         if(nums[i]+nums[j]==target){
//        //             return new int[] {i,j};
//        //         }
//        //     }
//        // }
//        // return null;
//    }
//
//    public boolean isPalindrome(String s) {
////        String[] split = s.split("\\pP|\\pS|\\s+");
//        char[] splitChar = s.toLowerCase().toCharArray();
//        StringBuilder ans = new StringBuilder();
//        for (char c : splitChar) {
//            if (c >= 'a' && c <= 'z' || c >= '0' && c <= '9') {
//                ans.append(c);
//            }
//        }
//        int left = 0, right = ans.length() - 1;
//        while (left < right) {
//            if (ans.charAt(left++) != ans.charAt(right--)) {
//                return false;
//            }
//        }
//        return true;
//    }
//
//    public List<String> fullJustify(String[] words, int maxWidth) {
//        List<String> ans = new ArrayList<>();
//        int right = 0, n = words.length;
//        while (true) {
//            int left = right; // 当前行的第一个单词在 words 的位置
//            int sumLen = 0; // 统计这一行单词长度之和
//            // 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格
//            while (right < n && sumLen + words[right].length() + right - left <= maxWidth) {
//                sumLen += words[right++].length();
//            }
//
//            // 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
//            if (right == n) {
//                StringBuffer sb = join(words, left, n, " ");
//                sb.append(blank(maxWidth - sb.length()));
//                ans.add(sb.toString());
//                return ans;
//            }
//
//            int numWords = right - left;
//            int numSpaces = maxWidth - sumLen;
//
//            // 当前行只有一个单词：该单词左对齐，在行末填充剩余空格
//            if (numWords == 1) {
//                StringBuffer sb = new StringBuffer(words[left]);
//                sb.append(blank(numSpaces));
//                ans.add(sb.toString());
//                continue;
//            }
//
//            // 当前行不只一个单词
//            int avgSpaces = numSpaces / (numWords - 1);
//            int extraSpaces = numSpaces % (numWords - 1);
//            StringBuffer sb = new StringBuffer();
//            sb.append(join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1))); // 拼接额外加一个空格的单词
//            sb.append(blank(avgSpaces));
//            sb.append(join(words, left + extraSpaces + 1, right, blank(avgSpaces))); // 拼接其余单词
//            ans.add(sb.toString());
//        }
//    }
//
//    // blank 返回长度为 n 的由空格组成的字符串
//    public String blank(int n) {
//        StringBuffer sb = new StringBuffer();
//        for (int i = 0; i < n; ++i) {
//            sb.append(' ');
//        }
//        return sb.toString();
//    }
//
//    // join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串
//    public StringBuffer join(String[] words, int left, int right, String sep) {
//        StringBuffer sb = new StringBuffer(words[left]);
//        for (int i = left + 1; i < right; ++i) {
//            sb.append(sep);
//            sb.append(words[i]);
//        }
//        return sb;
//    }
//
//
//    public List<String> fullJustify1(String[] words, int maxWidth) {
//
//        List<String> strings = new ArrayList<>();
//        int len = words[0].length();
//        int numLen = 0;
//        StringBuilder str = new StringBuilder();
//        int j = 0, flag = 0;
//        for (int i = 1; i < words.length; i++) {
//            numLen += words[i].length();
//            len += 1 + words[i].length();
//            if (len > maxWidth) {
//                int blankNum = maxWidth - numLen + words[i].length();
////                int rightNum = blankNum / i;
//                int leftNum = (int) ceil((double) blankNum / (i - 1));
//                flag = i - 2;
//                while (j < i) {
//                    str.append(words[j]);
//                    j++;
//                    while (leftNum != 0) {
//                        str.append(" ");
//                        leftNum--;
//                        blankNum--;
//                    }
//                    if (flag != 0) leftNum = blankNum / flag;
//
//                    flag--;
//                }
//                j = i;
//                len = words[i].length();
//                strings.add(str.toString());
//                str = new StringBuilder();
//            }
//        }
//
//        return strings;
//    }
//
//    public double myPow(double x, int n) {
//        int N = n;
//        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
//
//        // double ans = x;
//        // if(n==0) return 1;
//        // else if(n<0){
//        //     for(int i=1;i<-n;i++){
//        //         ans *= x;
//        //     }
//        //     return 1/ans;
//        // }else{
//        //     for(int i=1;i<n;i++){
//        //     ans *= x;
//        //     }
//        //     return ans;
//        // }
//    }
//
//    public double quickMul(double x, long N) {
//        if (N == 0) return 1.0;
//        double y = quickMul(x, N / 2);
//        return N % 2 == 0 ? y * y : y * y * x;
//    }
//
//    public int strStr(String haystack, String needle) {
//        return haystack.indexOf(needle);
//    }
//
//    public String convert(String s, int numRows) {
//        int n = s.length();
//        if (numRows == 1 || numRows >= n) {
//            return s;
//        }
//        StringBuilder[] mat = new StringBuilder[numRows];
//        for (int i = 0; i < numRows; ++i) {
//            mat[i] = new StringBuilder();
//        }
//        int x = 0;
//        int t = (numRows - 1) * 2;
//        for (int i = 0; i < n; ++i) {
//            mat[x].append(s.charAt(i));
//            if (i % t < numRows - 1) {
//                ++x;
//            } else {
//                --x;
//            }
//        }
//        StringBuilder ans = new StringBuilder();
//        for (StringBuilder row : mat) {
//            ans.append(row);
//        }
//        return ans.toString();
//    }
//
//    public String reverseWords(String s) {
//        /**
//         * "luffy is still joyboy " --》split: ["luffy","is","still","joyboy"]
//         */
//        // 分割字符串为字符串数组
//        String[] split = s.split(" ");
//
//        // 使用StringBuilder--》 字符串可变
//        StringBuilder ans = new StringBuilder();
//
//        // 保证后续往ans添加数据时 直接在新数据前面直接加一个“ ”空格就好
//        ans.append(split[split.length - 1]);
//
//        // 遍历split数组，每次加入时不要忘记 “空格”
//        for (int i = split.length - 2; i >= 0; i--) {
//            if (!"".equals(split[i])) {
//                ans.append(" ").append(split[i]);
//            }
//        }
//        return ans.toString();
//
////        StringBuilder ans = new StringBuilder();
////        int flag = 0;
////        String trimmed = s.trim();
////        String string = new StringBuilder(trimmed).reverse().toString();
////        for (int i = 0; i <= string.length(); i++) {
////            if (i == string.length() || string.charAt(i) == ' ') {
////                ans.append(new StringBuilder(string.substring(flag, i)).reverse());
////                flag = i;
////            }
////        }
////        return ans.toString();
//    }
//
//    public int mySqrt(int x) {
//        int low = 0, high = x, ans = -1;
//        while (low <= high) {
//            int mid = low + (high - low) / 2;
//            if ((long) mid * mid <= x) {
//                ans = mid;
//                low = mid + 1;
//            } else {
//                high = mid - 1;
//            }
//        }
//        return ans;
//    }
//
//    public int[] numberGame(int[] nums) {
//        Arrays.sort(nums);
//        int[] ans = new int[nums.length];
//        ans[0] = nums[1];
//        ans[1] = nums[0];
//        if (nums.length % 2 != 0) {
//            ans[nums.length - 1] = nums[nums.length - 1];
//            for (int i = 2; i < nums.length - 1; i++) {
//                if (i % 2 == 0) {
//                    ans[i] = nums[i + 1];
//                } else {
//                    ans[i] = nums[i - 1];
//                }
//
//            }
//        } else {
//            for (int i = 2; i < nums.length; i++) {
//                if (i % 2 == 0) {
//                    ans[i] = nums[i + 1];
//                } else {
//                    ans[i] = nums[i - 1];
//                }
//            }
//        }
//        return ans;
//    }
//
//    public int lengthOfLastWord(String s) {
//        int len = s.length();
//        char[] charS = s.toCharArray();
//        int i;
//        for (i = len - 1; i >= 0; i--) {
//            if (charS[i] == ' ') {
//                charS[i] = '|';
//            } else {
//                break;
//            }
//        }
//        String ans = new String(charS);
//        return i - ans.lastIndexOf(" ");
//    }
//
//    public int trailingZeroes(int n) {
//        int ans = 0;
//        for (int i = 5; i <= n; i++) {
//            for (int x = i; x % 5 == 0; x /= 5) {
//                ans++;
//            }
//        }
//        return ans;
//    }
//
//    public String getChar(int n) {
//        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
//
//        switch (n) {
//            case 1:
//                return "I";
//            case 5:
//                return "V";
//            case 10:
//                return "X";
//            case 50:
//                return "L";
//            case 100:
//                return "C";
//            case 500:
//                return "D";
//            case 1000:
//                return "M";
//            case 900:
//                return "CM";
//            case 400:
//                return "CD";
//            case 90:
//                return "XC";
//            case 40:
//                return "XL";
//            case 9:
//                return "IX";
//            case 4:
//                return "IV";
//            default:
//                return "";
//        }
//    }
//
//    public int getValue(char s) {
//        switch (s) {
//            case 'I':
//                return 1;
//            case 'V':
//                return 5;
//            case 'X':
//                return 10;
//            case 'L':
//                return 50;
//            case 'C':
//                return 100;
//            case 'D':
//                return 500;
//            case 'M':
//                return 1000;
//            default:
//                return 0;
//        }
//    }
//
//    public int romanToInt(String s) {
//        int len = s.length();
//        int ans = getValue(s.charAt(len - 1));
//        for (int i = len - 2; i >= 0; i--) {
//            int tmp = getValue(s.charAt(i + 1));
//            int cur = getValue(s.charAt(i));
//            if (cur >= tmp) {
//                ans += getValue(s.charAt(i));
//            } else {
//                ans -= getValue(s.charAt(i));
//            }
//        }
//        return ans;
//    }
//
//    public int trap(int[] height) {
//        int len = height.length;
//        int[] left = new int[len];
//        int[] right = new int[len];
//        int ans = 0;
//        left[0] = 0;
//        right[len - 1] = 0;
//        for (int i = 1; i < len; i++) {
//            left[i] = Math.max(left[i - 1], height[i - 1]);
//        }
//        for (int i = len - 2; i >= 0; i--) {
//            right[i] = Math.max(height[i + 1], right[i + 1]);
//        }
//        for (int i = 1; i < len - 1; i++) {
//            int flag = Math.min(left[i], right[i]) - height[i];
//            if (flag > 0) ans += flag;
//        }
//        return ans;
//    }
//
//    public int[] plusOne(int[] digits) {
//        int len = digits.length;
//        int[] help = new int[len + 1];
//        int[] ans = new int[len];
//        System.arraycopy(digits, 0, help, 1, len + 1 - 1);
//        if (help[len] != 9) {
//            help[len] += 1;
//        } else {
//            help[len] = 0;
//            int i = len - 1;
//            while (help[i] == 9 && i >= 1) {
//                help[i] = 0;
//                i--;
//            }
//            help[i] += 1;
//        }
//        if (help[0] == 0) {
//            System.arraycopy(help, 1, ans, 0, len + 1 - 1);
//        } else {
//            return help;
//        }
//        return ans;
//    }
//
//    public int candy(int[] ratings) {
//        int len = ratings.length;
//        int[] ans = new int[len];
//        Arrays.fill(ans, 1);
//        int min = 1, sum = 0;
//        for (int i = 1; i < len; i++) {
//            min = Math.min(min, ans[i]);
//            if (ratings[i] > ratings[i - 1]) {
//                ans[i] = ans[i - 1] + 1;
//
//            } else if (ratings[i] == ratings[i - 1]) {
//                ans[i] = min;
//            } else {
//                if (ans[i - 1] == min) {
//                    ans[i] = ans[i - 1] - 1;
//                } else {
//                    ans[i] = min;
//                }
//            }
//            min = Math.min(min, ans[i]);
//        }
//        for (int i = 0; i < len; i++) {
//            if (min == 0) {
//                ans[i] += 1;
//            } else if (min < 0) {
//                ans[i] -= (min - 1);
//            }
//            sum += ans[i];
//        }
//        return sum;
//    }
//
//    int[] left; // 保存以每个字符为中心的最长回文子串的长度（左侧）
//    int[] right; // 保存以每个字符为中心的最长回文子串的长度（右侧）
//    char[] chars; // 字符数组，存储字符串s的字符
//    int[] sumxor; // 计算中心扩展时使用的数组
//    long[] sum; // 计算中心扩展时使用的数组
//
//    public long maxProduct(String s) {
//        chars = s.toCharArray();
//        int len = chars.length;
//        if (len < 4) // 字符串长度小于4，无法找到两个奇数长度的回文子串，返回1
//            return 1;
//        left = new int[len];
//        right = new int[len];
//        int max = left[0] = left[1] = right[len - 1] = right[len - 2] = 1;
//        sumxor = new int[len];
//        sum = new long[len];
//        sum[0] = 0;
//        sumxor[0] = chars[0];
//        sum[1] = 0;
//        sumxor[1] = sumxor[0] ^ chars[1];
//        int k;
//        for (int i = 0, j = 2; j < len; j++) { // 遍历字符串
//            k = j - 1;
//            sumxor[j] = sumxor[k] ^ chars[j]; // 计算中心扩展时需要的sumxor数组
//            sum[j] = sum[k] + (long) (chars[k] - chars[k - 1] + chars[j] - chars[k]) * (chars[k - 1] + chars[j] + chars[k]); // 计算中心扩展时需要的sum数组
//            if (chars[i] == chars[j] && judge(i, j)) { // 判断当前字符和已有回文子串的右侧字符是否相等，并通过judge函数判断是否是回文子串
//                left[j] = j - i + 1;
//                max = left[j];
//                if (i > 0) i--; // i左移
//                else {
//                    j++;
//                    if (j < len) {
//                        left[j] = max;
//                        sumxor[j] = sumxor[k + 1] ^ chars[j];
//                        sum[j] = sum[k + 1] + (long) (chars[k + 1] - chars[k] + chars[j] - chars[k + 1]) * (chars[k] + chars[j] + chars[k + 1]);
//                    }
//                }
//            } else {
//                left[j] = max;
//                i++; // i右移
//            }
//        }
//        long res = Math.max(left[len - 2], left[len - 3]); // 保存第一个回文子串
//        max = 1;
//        for (int i = len - 1, j = len - 3; j > 0; j--) { // 右侧回文子串从右向左遍
//            if (chars[i] == chars[j] && judge(j, i)) { // 判断当前字符和已有回文子串的左侧字符是否相等，并通过judge函数判断是否是回文子串
//                right[j] = i - j + 1;
//                max = right[j];
//                res = Math.max(res, (long) right[j] * left[j - 1]); // 计算两个回文子串长度的乘积，并与之前的结果比较取较大值
//                if (i < len - 1) i++; // i右移
//                else {
//                    j--;
//                    if (j > 0) {
//                        right[j] = max;
//                        res = Math.max(res, (long) right[j] * left[j - 1]); // 计算两个回文子串长度的乘积，并与之前的结果比较取较大值
//                    }
//                }
//            } else {
//                right[j] = max;
//                res = Math.max(res, (long) right[j] * left[j - 1]); // 计算两个回文子串长度的乘积，并与之前的结果比较取较大值
//                i--; // i左移
//            }
//        }
//        return res; // 返回最大的乘积结果
//    }
//
//    int m;
//
//    boolean judge(int i, int j) { // 判断给定下标范围内的子串是否是回文子串
//        m = (i + j) >> 1; // 计算中间位置
//        if (i > 0)
//            return (sumxor[j] ^ sumxor[i - 1]) == chars[m] && chars[m - 1] == chars[m + 1] && sum[j] == sum[i + 1];
//        return sumxor[j] == chars[m] && chars[m - 1] == chars[m + 1] && sum[j] == 0;
//    }

}